题解 | #还是畅通工程#

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