题解 | 继续畅通工程

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct myType {
    int v1;
    int v2;
    int weight;
    int xj;
    myType(int _v1, int _v2, int _weight, int _xj) {
        v1 = _v1;
        v2 = _v2;
        weight = _weight;
        xj = _xj;
    }
};
bool compare(myType lhs, myType rhs) {
    if (lhs.xj > rhs.xj) {
        return true;
    }
    else if (lhs.xj < rhs.xj) {
        return false;
    }
    else {
        if (lhs.weight < rhs.weight) {
            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 (father[u] == 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, weight, xj;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) { break; }
        vector<myType> p;
        InitT(n+1);
        int total = 0;
        int vertex = 0;
        for (int i = 0; i < n * (n - 1) / 2; ++i) {
            scanf("%d%d%d%d", &v1, &v2, &weight, &xj);
            myType e(v1, v2, weight, xj);
            p.push_back(e);
        }
        sort(p.begin(), p.end(), compare);
        for (int j = 0; j < n * (n - 1) / 2; ++j) {
            if (vertex == n - 1) { break; }
            if (FindT(p[j].v1) != FindT(p[j].v2)) {
                vertex++;
                UnionT(p[j].v1, p[j].v2);
                if (p[j].xj == 0) { total += p[j].weight; }
            }
        }
        printf("%d\n", total);
    }
    return 0;
}