题解 | #还是畅通工程#

#include <iostream>
#include <algorithm>
using namespace std;

struct Edge{
    int from;
    int to;
    int length;
};

const int MAX=1000;
Edge edge[MAX*MAX];

int father[MAX];
int height[MAX];

void initial(int n){
    for(int i=1;i<=n;i++){
        father[i]=i;
        height[i]=0;
    }
}

int find(int x){
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}

void Union(int a,int b){
    a=find(a);
    b=find(b);
    if(a!=b){
        if(height[a]<height[b]) father[a]=b;
        else if(height[a]>height[b]) father[b]=a;
        else{
            father[a]=b;
            height[b]++;
        }
    }
}

bool comp(Edge a,Edge b){
    return a.length<b.length;
}


int Kruscal(int n,int edgeLength){
    initial(n);//初始化
    sort(edge,edge+edgeLength,comp);//升序排列
    int sum=0;//总长度
    for(int i=1;i<=edgeLength;i++){
        Edge current = edge[i];
        if(find(current.from)!=find(current.to)){//从小到大边加入到集合中
            Union(current.from,current.to);
            sum+=current.length;
        }
    }
    return sum;
}



int main() {
    int n;
    while(cin>>n){
        if(n==0) break;
        int edgeLength=n*(n-1)/2;
        for(int i=1;i<=edgeLength;i++){
            cin>>edge[i].from>>edge[i].to>>edge[i].length;
        }
        int answer=Kruscal(n,edgeLength);
        cout<<answer<<endl;
    }
}
// 64 位输出请用 printf("%lld")