题解 | 还是畅通工程

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct myType {
    int v1c;
    int v2c;
    int milec;
};
bool compare(myType lhs, myType rhs) {
    if (lhs.milec < rhs.milec) {
        return true;
    }
    else {
        return false;
    }
}
int father[100];
void InitT(int n) {
    for (int i = 0; i <= n; ++i) {
        father[i] = i;
    }
}
int FindT(int u) {
    if (u == father[u]) { return u; }
    else {
        father[u] = FindT(father[u]);
        return father[u];
    }
}
void UnionT(int u, int v) {
    int uroot = FindT(u);
    int vroot = FindT(v);
    father[vroot] = uroot;
}
int main() {
    int n;
    int v1, v2, mile;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) { break; }
        InitT(n);
        int vertex = 0;
        int minmile = 0;
        vector<myType> my(n * (n - 1) / 2);
        for (int i = 0; i < n * (n - 1) / 2; ++i) {
            scanf("%d%d%d", &v1, &v2, &mile);
            my[i].v1c = v1;
            my[i].v2c = v2;
            my[i].milec = mile;
        }
        sort(my.begin(), my.end(), compare);
        for (int j = 0; j < n * (n - 1) / 2; ++j) {
            if (vertex == n - 1) { break; }
            if (FindT(my[j].v1c) != FindT(my[j].v2c)) {
                UnionT(my[j].v1c, my[j].v2c);
                ++vertex;
                minmile = minmile + my[j].milec;
            }
        }
        if (minmile != 0) { printf("%d\n", minmile); }

    }
    return 0;
}