题解 | #还是畅通工程#

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

const int MAXN = 10000+10;

struct Edge {
    int from;
    int to;
    int length;
};
Edge edge[MAXN];
int father[MAXN];
int height[MAXN];
void Initial(int n){
    for(int i=0;i<n;i++){
        father[i] = i;
        height[i] = 0;
    }
}
bool Compare(Edge x,Edge y){
    return x.length<y.length;
}
int Find(int n){
    if(father[n] != n){
        father[n] = Find(father[n]);
    }
    return father[n];
}
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[b] = a;
            height[a]++;
        }
    }
}
int Kruskal(int n,int num){
    int len = 0;
    for(int i=0;i<num;i++){
        if(Find(edge[i].from) != Find(edge[i].to)){
            Union(edge[i].from,edge[i].to);
            len+=edge[i].length;
        }
    }
    return len;
}
int main() {
    int n;
    while (cin >> n) { 
        if(n == 0){
            break;
        }
        Initial(n);
        int m = n*(n-1)/2;
        for(int i=0;i<m;i++){
            cin>>edge[i].from>>edge[i].to>>edge[i].length;
        }
        sort(edge,edge+m,Compare);
        int ans = Kruskal(n,m);
        cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")