hdu 1233 还是畅通工程(最小生成树，kruskal，前向星)

本文主要是介绍hdu 1233 还是畅通工程(最小生成树，kruskal，前向星)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1233

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{int from,to,w;bool operator<(const Edge b)const{return w<b.w;}
}edge[5000];
int father[100];
int find(int a){if(father[a]==a)return a;return find(father[a]);
}
int kruskal(int n){int ans=0,top=0,i;for(i=1;i<=n;i++){father[i]=i;}for(i=0;i<n*(n-1)/2;i++){if(top==n-1)break;int q1=find(edge[i].from),q2=find(edge[i].to);if(q1!=q2){ans+=edge[i].w;father[q1]=q2;top++;}}return ans;
}
int main()
{//freopen("cin.txt","r",stdin);int n,i;while(cin>>n&&n){memset(father,0,sizeof(father));for(i=0;i<n*(n-1)/2;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);edge[i].from=a;edge[i].to=b;edge[i].w=c;}sort(edge,edge+n*(n-1)/2);printf("%d\n",kruskal(n));}return 0;
}

这篇关于hdu 1233 还是畅通工程(最小生成树，kruskal，前向星)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---