题解 | #继续畅通工程#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(vector<int> lhs, vector<int> rhs) {
    if(lhs[3]==1&&rhs[3]==0){
        return false;
    }else if(lhs[3]==0&&rhs[3]==1){
        return true;
    }
    return lhs[2] < rhs[2];
}

int father[1000];
int findfather(int u) {
    if (father[u] == u) {
        return u;
    } else {
        return findfather(father[u]);
    }
}
void unionset(int u, int v) {
    int u1 = findfather(u);
    int v1 = findfather(v);
    father[v1] = u1;
}
void initate(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        initate(n+1);
        if (n == 0) break;
        int sum = 0;
        vector < vector<int>> edge(n* (n - 1) / 2);
        int tmp1,tmp2,tmp3,tmp4;
        for (int i = 0; i < n * (n - 1) / 2; i++) {
            scanf("%d%d%d%d", &tmp1, &tmp2, &tmp3, &tmp4);
            int notbuild = 0;
            if (tmp4 == 1) unionset(tmp1, tmp2);
                edge[i].push_back(tmp1);
                edge[i].push_back(tmp2);
                edge[i].push_back(tmp3);
                edge[i].push_back(tmp4);
            }
        
        sort(edge.begin(), edge.end(), cmp);
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (father[i] == i) count++;
        }
        int no = 0;
        for (int i = 0; i < count - 1; i++) {
            while (findfather(edge[no][0]) == findfather(edge[no][1])) {
                no++;
            }
            sum += edge[no][2];
            unionset(edge[no][0],edge[no][1]);
        }
        edge.clear();
        printf("%d\n",sum);
    }
}