1 struct edge 2 { 3 int start,to,value; //起点、终点和权值，value的值可以不是整型 4 bool operator <(edge a)const //重载运算符，作用相当于一个cmp函数 5 { 6 return value<a.value; 7 } 8 }e[num_edge];
·利用并查集，来判断点是否连通：
1 int union_find(int x) 2 { 3 int r=x; 4 while(pre[r]!=r) //寻找祖先。这样的话，我们就需要一个pre数组记录这个点的祖先 5 { 6 r=pre[r]; 7 } 8 int i=x,j; 9 while(i!=r) //路径压缩，可不加 10 { 11 j=pre[i]; 12 pre[i]=r; 13 i=j; 14 } 15 return r; 16 }
有了这两个工具，我们就可以用代码来实现Kruskal了：
void kruskal() { int i; total=0; //记录已经加入图中的边的数量 val=0; //记录权值之和 for(i=0;i<m;i++) //遍历边 { int u,v; u=union_find(e[i].start); v=union_find(e[i].to); if(u==v) continue; //判断这个边的两点是否连通，如连通，则跳过 total++; pre[u]=v; //将两点更新为连通 val+=e[i].value; if(total==n-1) break; //若total=n-1则已经生成最小生成树，可跳出循环了 } return ; }
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int pre[5005],n,m,val,total; 6 7 struct edge 8 { 9 int start,to,value; 10 bool operator <(edge a)const 11 { 12 return value<a.value; 13 } 14 }e[200005]; 15 16 int union_find(int x) 17 { 18 int r=x; 19 while(pre[r]!=r) 20 { 21 r=pre[r]; 22 } 23 int i=x,j; 24 while(i!=r) 25 { 26 j=pre[i]; 27 pre[i]=r; 28 i=j; 29 } 30 return r; 31 } 32 33 void kruskal() 34 { 35 int i; 36 total=0; 37 val=0; 38 for(i=0;i<m;i++) 39 { 40 //cout<<"test"<<‘ ‘; 41 int u,v; 42 u=union_find(e[i].start); 43 v=union_find(e[i].to); 44 // cout<<u<<‘ ‘<<v<<‘*‘<<endl; 45 if(u==v) continue; 46 total++; 47 pre[u]=v; 48 val+=e[i].value; 49 if(total==n-1) break; 50 } 51 } 52 53 int main() 54 { 55 int i; 56 scanf("%d%d",&n,&m); 57 for(i=0;i<n;i++) pre[i]=i; 58 for(i=0;i<m;i++) scanf("%d%d%d",&e[i].start,&e[i].to,&e[i].value); 59 sort(e,e+m); 60 kruskal(); 61 //cout<<total<<‘*‘<<endl; 62 if(total==n-1) printf("%d",val); 63 else printf("orz"); 64 return 0; 65 }
其他题目：
Luogu P2330 [SCOI2005]繁忙的都市（难度：☆）
Luogu P2872 [USACO07DEC]道路建设Building Roads（难度：★）
Luogu P2504 [HAOI2006]聪明的猴子（难度：★）
Luogu P2212 [USACO14MAR]浇地Watering the Fields（难度：★☆）
Author:Houge Date:2019.5.25
原文：https://www.cnblogs.com/CSGOBESTGAMEEVER/p/10923099.html
