题解 | #继续畅通工程#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define N 100010

int father[N];
int height[N];


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

vector<Edge> vec;

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[y] = x;
            height[x]++;
        }
    }

}

bool compare(Edge l, Edge r) {
    return l.weight < r.weight;
}

void Kruskal(int n, int &total) {
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        Union(vec[i].x, vec[i].y, vec[i].weight, total);
    }
    return;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        Init(n);
        for (int i = 0; i < n*(n-1)/2 ; i++) {
            Edge edge;
            int flag;
            scanf("%d%d%d%d", &edge.x, &edge.y, &edge.weight, &flag);
            if (flag == 1) {
                //修缮好，权值当0
                edge.weight = 0;
            }
            vec.push_back(edge);
        }
        int total = 0;
        sort(vec.begin(), vec.end(), compare);
        Kruskal(n, total);
        vec.clear();
        cout << total << endl;
    }

    return 0;
};