克鲁斯卡尔算法 模板题hdu 1233
还是畅通工程
当N为0时,输入结束,该用例不被处理。
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
3 5Huge input, scanf is recommended.HintHint
//考查知识点:克鲁斯卡尔算法 #include<stdio.h> #include<algorithm> using namespace std; int n,m; struct node{ int sta,end,wei; }s[11000]; int father[11000]; int cmp(node x,node y) { return x.wei<y.wei; } int find(int x) { return x==father[x]?x:find(father[x]); } //int find(int x) //{ // int r=x; // while(r!=father[r]) // r=father[r]; // int j=x; // while(j!=r) // { // int k=father[j]; // father[j]=r; // j=k; // } // return r; //} void kruskal() { int i,j,sum=0; for(i=1;i<=m;++i) { int fa=find(s[i].sta); int fb=find(s[i].end); if(fa!=fb) { sum+=s[i].wei; father[fa]=fb; } } printf("%d\n",sum); } int main() { // int n; while(~scanf("%d",&n),n) { m=n*(n-1)/2; int i,j; for(i=1;i<=n;++i) father[i]=i; for(i=1;i<=m;++i) { scanf("%d%d%d",&s[i].sta,&s[i].end,&s[i].wei); } sort(s+1,s+m+1,cmp); kruskal(); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。