题解 | #还是畅通工程#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct edge{
    int x;
    int y;
    int weight;
    edge(int x,int y,int w):x(x),y(y),weight(w){}
};

const int N = 100;
int father[N];
int height[N];

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

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

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

bool compare(edge lhs,edge rhs){
    return lhs.weight < rhs.weight;
}

int main(){
    int n,x,y,w;
    vector<edge> eV;
    while (cin>>n){
        if (n==0) break;

        Init(n);
        for (int i = 0; i < n*(n-1)/2; ++i) {
            cin>>x>>y>>w;
            eV.push_back(edge(x,y,w));
        }
        sort(eV.begin(),eV.end(), compare);
        int total = 0;
        for (int i = 0; i < n*(n-1)/2; ++i) {
            Union(eV[i].x,eV[i].y,eV[i].weight,total);
        }
        cout<<total<<endl;
    }
}