给定一个无向图，从中选出若干条边，使得选出的边构成一棵树（任意两点有且仅有一条路径相互到达），且选出的边权值和最小，那么选出的边以及点就构成了一颗最小生成树
Kruskal的算法流程如下：
1.建立并查集，每个点各自构成一个集合。
2.把所有边按照权值从小到大排序，依次扫描每条边(x,y,z)
3.如果x,y属于同一集合，则忽略这条边，继续继续扫描下一条边。
4.否则，合并x,y所在的集合，并把z累加到答案中。
5.所有边扫描完后，第4步中所处理过的边就构成最小生成树
时间复杂度为O(nlogn)
具体来说就是这样：
struct edge{int x,y,z;}a[30005];
bool cmp(const edge &x,const edge &y){return x.z<y.z;}
int n,m,ans=0,prt[3005];
int Getfather(int x)
{
if(prt[x]==x)return x;
return prt[x]=Getfather(prt[x]);
}
void kruskal()
{
int k=0;
for(int i=1;i<=n;i++)prt[i]=i;
for(int i=1;i<=m;i++)
{
int f1,f2;
f1=Getfather(a[i].x);
f2=Getfather(a[i].y);
if(f1==f2)continue;
prt[f1]=f2;
ans+=a[i].z;
k++;
if(k==n-1)return;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
kruskal();
cout<<ans;
return 0;
}
花开·花落--便是一生 