最小生成树---Kruskal算法

2018-12-04 07:13:52来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

~~已会各位大佬们可以跳过QwQ~~,today,we will use a magical algorithm!let is go!

不显摆了(也没得显摆),今天我们用Kruskal算法来解这道题。

1. 定义

int fa[1000100],i,j,k,n,m,s,ans;//基本变量:)
struct eige{

int x,y,z;

}a[1000100];//主要是为了排序

 

 

2. 排序函数定义

int cmp(eige u,eige v){
return u.z<v.z;//将边长从小到大排好;)
}

 



接下来让我们一起来做一件伟大的事情———并查集!(详见博客)
[点这也可以](http://baidu.apphb.com/?q=并查集),
因为如果两个点在不同集合则合并为树,否则跳过。

开始查集

int find(int x){
if(x==fa[x]){//是不是同一个boss
return x;
}
else return fa[x]=find(fa[x]);
}

 



好了,让我们打主程序吧ヾ(??▽?)ノ▄︻┻┳══━一

 //输入跳过
sort(a+1,a+1+m,cmp);//排个序
for(i=1;i<=n;i++){
fa[i]=i;//所有人的父节点是自己
}
for(i=1;i<=m;i++){
if(find(a[i].x)!=find(a[i].y)){//看看两个人在不在同一集合
fa[find(a[i].x)]=find(a[i].y);//不是则合并
s++;
ans+=a[i].z;//累加树边长度
if(s>=n-1){
break;
}
}
}
if(s<n-1){
cout<<"orz"<<endl;//不要忘了这个(其实有没有似乎没有关系)
return 0;
}
//输出啥的......不说 :)

 

大佬勿喷即可qvq

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:利用ZYNQ SOC快速打开算法验证通路(6)——利用AXI总线实时配置

下一篇:音频算法之小黄人变声 附完整C代码