好贷网好贷款

hdu 1233 还是畅通工程 Kruskal 最小生成树 并查集

发布时间:2016-12-4 5:57:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1233 还是畅通工程 Kruskal 最小生成树 并查集",主要涉及到hdu 1233 还是畅通工程 Kruskal 最小生成树 并查集方面的内容,对于hdu 1233 还是畅通工程 Kruskal 最小生成树 并查集感兴趣的同学可以参考一下。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1233 模板题,kruskal求最小生成树。 并查集是个好东西啊  就是注意一点 输入边的信息时,角标应该是从0开始的 代码: #include<iostream> #include<algorithm> #include<cstdio> using namespace std; struct edge { int u; int v; int w; }; int p[100]; edge e[5000]; bool cmp(edge a,edge b) { return a.w<b.w; } int find(int x) { if(p[x]==x) return x; else { return p[x]=find(p[x]); } } int n,m; long long kruskal() { for(int i=0;i<n;i++) p[i]=i; long long ans=0; for(int i=0;i<m;i++) { int x=find(e[i].u); int y=find(e[i].v); if(x!=y) { ans+=e[i].w; p[x]=y; } } return ans; } int main() { while(cin>>n) { if(n==0) break; m=n*(n-1)/2; int a,b,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); e[i].u=a-1; e[i].v=b-1; e[i].w=c; } sort(e,e+m,cmp); cout<<kruskal()<<endl; } }

上一篇:C++引用本质
下一篇:C#.NET学习笔记1---C#.NET简介

相关文章

相关评论