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;} }

转载于:https://www.cnblogs.com/814jingqi/p/3339270.html

总结

以上是生活随笔为你收集整理的hdu 1233 还是畅通工程 Kruskal 最小生成树 并查集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。