题解 | #还是畅通工程#

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 1000
int total=0;
int father[N];
int height[N];
struct Edge{
    int x;
    int y;
    int weight;
};
void Init(int n){
    for (int i = 1; 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 x,int y,int weight){
    x= Find(x);
    y= Find(y);
    if (x!=y) {
        total += weight;
    }
    if(height[x]<height[y]){
        father[x]=y;
    }else if (height[x]>height[y]){
        father[y]=x;
    }else{
        father[y]=x;
        ++height[x];
    }
}
bool comp(Edge lhs,Edge rhs){
    return lhs.weight<rhs.weight;
}
int main(){
    int n;
    while (scanf("%d",&n)!=EOF) {
        if (n == 0) {
            break;
        }
        Init(n);
        vector<Edge> vec;
        for (int i = 0; i < n * (n - 1) / 2; ++i) {
            Edge edge;
            scanf("%d%d%d", &edge.x, &edge.y, &edge.weight);
            vec.push_back(edge);
        }
        total=0;
        sort(vec.begin(), vec.end(), comp);
        for (int i = 0; i < n * (n - 1) / 2; ++i) {
            Union(vec[i].x, vec[i].y, vec[i].weight);
        }
        printf("%d\n", total);
    }
}