题解 | #还是畅通工程#
还是畅通工程
https://www.nowcoder.com/practice/d6bd75dbb36e410995f8673a6a2e2229
//最小生成树:边权和最小的一棵树 #include <iostream> #include<algorithm> using namespace std; struct Edge{ int from; int to; int length; bool operator<(const Edge& e)const{ return length<e.length; } }; Edge edge[5000]; int father[100]; int height[100]; void Initial() { for(int i=0;i<100;i++) { father[i]=i; height[i]=0; } } int Find(int x) { if(x==father[x])return x; else{ return Find(father[x]); } } void Union(int a,int b) { a=Find(a); b=Find(b); if(a!=b) { if(height[a]>height[b])father[b]=a; else if(height[a]<height[b])father[a]=b; else { father[b]=a; height[a]++; } } } int Kruskal(int n,int edgenumber) { int answer=0; for(int i=0;i<edgenumber;i++) { if(Find(edge[i].from)!=Find(edge[i].to)) { Union(edge[i].from,edge[i].to); answer+=edge[i].length; } } return answer; } int main() { int n; while (cin >> n) { if(n==0)break; int edgenumber=n*(n-1)/2; for(int i=0;i<edgenumber;i++) { cin>>edge[i].from>>edge[i].to>>edge[i].length; } sort(edge,edge+edgenumber); Initial(); cout<<Kruskal(n,edgenumber)<<endl; } }