题解 | 还是畅通工程

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

struct Node {
    int x;
    int y;
    int weight;
};

int root[100];

bool Compare(Node node1, Node node2) {
    return node1.weight < node2.weight;
}

int Find(int x) {
    while (x != root[x]) x = root[x];
    return x;
}//查

void Union(int x, int y) {
    int a = Find(x);
    int b = Find(y);
    root[a] = b;
}//并

void Init() {
    for (int i = 0; i < 100; i++) root[i] = i;
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        Init();
        int num = n * (n - 1) / 2;
        Node node[num];
        for (int i = 0; i < num; i++) {
            cin >> node[i].x >> node[i].y >> node[i].weight;
        }
        sort(node, node + num, Compare);
        int sum = 0;
        for (int i = 0; i < num; i++) {
            int a = Find(node[i].x);
            int b = Find(node[i].y);
            if (a != b) {
                Union(a, b);
                sum += node[i].weight;
            }
        }
        cout << sum << endl;
    }
}