最小生成树---Kruskal算法

~~已会各位大佬们可以跳过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

}

接下来让我们一起来做一件伟大的事情———并查集！（详见博客）

[点这也可以](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

cout<<"orz"<

return 0;

}

//输出啥的......不说 :)

大佬勿喷即可qvq

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!