题解 | #还是畅通工程#

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

using namespace std;

const int N = 110;

int p[N];
int height[N];


struct Edge{
    int a;
    int b;
    int w;
    bool operator < (const Edge& e) const{
        return w < e.w;
    }
    Edge(int x,int y,int z): a(x), b(y), w(z) {};
};

void init(int n) {
    for (int i = 1; i <= n; i++)p[i] = i, height[i] = 0;
}

int find(int a) {
    if (a != p[a])p[a] = find(p[a]);
    return p[a];
}

void cUnion(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x != y) {
        if (height[x] > height[y]) {
            p[y] = x;
        } else if (height[x] < height[y]) {
            p[x] = y;
        } else {
            p[x] = y;
            height[y] += height[x];
        }
    }
}

int kruskal(vector<Edge> edges){
    int ans=0;
    for(int i=0;i<edges.size();i++){
        int a = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;
        if(find(a)==find(b))continue;
        else{
            ans+=w;
            cUnion(a,b);
        }
    }

    return ans;

}

int main() {
    int n;
    while (cin >> n) {
        if(!n)break;
        init(n);
        int m = n*(n-1)/2;
        vector<Edge> edges;
        while (m--) {
            int a, b, w;
            cin >> a >> b >>w;
            edges.push_back(Edge(a,b,w));
        }
        sort(edges.begin(),edges.end());
        int ans = kruskal(edges);
        cout<<ans<<endl;
    }


}