九度OnlineJudge之1017：还是畅通工程
题目描述： #include <algorithm>#include <iostream>#define N 101using namespace std;struct Edge{ int a,b; int cost; bool operator < (const Edge& A)const { return cost<A.cost; } }Edge[6000];int Tree[N];int findRoot(int x){ if(Tree[x]==-1) return x; else { int tmp = findRoot(Tree[x]); Tree[x] = tmp; return tmp; } }int main(){ int n; while(cin>>n,n!=0) { for(int i=1;i<=n*(n-1)/2;i++) cin>>Edge[i].a>>Edge[i].b>>Edge[i].cost; sort(Edge+1,Edge+n*(n-1)/2+1);//按照权值从小到大给边排序 for(int i=1;i<=n;i++) Tree[i] = -1; int ans = 0;//最小生成树权值和 for(int i=1;i<=n*(n-1)/2;i++) { int a = Edge[i].a; int b = Edge[i].b; int c = Edge[i].cost; a = findRoot(a); b = findRoot(b); if(a!=b) { Tree[a] = b; ans += c; } } cout<<ans<<endl; } // system("PAUSE"); return 0;}
