克鲁斯卡尔算法 hdu 1863
畅通工程
行对应村庄间道路的成本,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间道路的成本(也是正整数)。为简单起见,村庄从1到M编号。当N为0时,全部输入结束,相应的结果不要输出。
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
3 ?
//考查知识点:克鲁斯卡尔算法 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct node{ int sta,end,wei; }s[110]; int n,m; int father[110]; int cmp(node x,node y) { return x.wei<y.wei; } 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; } //int find(int x) //{ // return x==father[x]?x:find(father[x]); //} void kruskal() { int i,j; int count=1; int sum=0; for(i=1;i<=n;++i) { int fa=find(s[i].sta); int fb=find(s[i].end); if(fa!=fb) { father[fa]=fb; sum+=s[i].wei; count++; } } if(count==m) printf("%d\n",sum); else printf("?\n"); } int main() { int i,j; while(~scanf("%d%d",&n,&m),n) { for(i=1;i<=m;++i) father[i]=i; for(i=1;i<=n;++i) { scanf("%d%d%d",&s[i].sta,&s[i].end,&s[i].wei); } sort(s+1,s+n+1,cmp); kruskal(); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。