题解 | #继续畅通工程#

#include <stdio.h>
#include <stdlib.h>

struct Edge {
    int from;
    int to;
    int cost;
    int build;
};

int father[100];
struct Edge e[100 * 100];
int height[100];

void initial(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}



int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b])
            father[a] = b;
        else if (height[a] > height[b])
            father[b] = a;
        else {
            father[a] = b;
            height[b]++;
        }
    }
}

int cmp(const void* a, const void* b) {
    const struct Edge* a1 = (const struct Edge*)a;
    const struct Edge* b1 = (const struct Edge*)b;
    if (a1->cost > b1->cost)
        return 1;
    if (a1->cost < b1->cost)
        return -1;
    return 0;
}

void initialF(struct Edge e[], int m){
    for(int i = 0; i < m; i++){
        if (e[i].build == 1){
            Union(e[i].from, e[i].to);
        }
    }
}

int KrusKal(struct Edge e[], int m) {
    initialF(e, m);
    int ans = 0;
    qsort(e, m, sizeof(struct Edge), cmp);
    for (int i = 0; i < m; i++) {
        if (Find(e[i].to) != Find(e[i].from) && e[i].build == 0) {
            Union(e[i].to, e[i].from);
            ans += e[i].cost;
        }
    }
    return ans;
}

int main() {
    int n, m, count = 0, f, t, c, bui;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        initial(n);
        m = n * (n - 1) / 2;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &f, &t, &c, &bui);
            e[i].to = t;
            e[i].from = f;
            e[i].cost = c;
            e[i].build = bui; // 初始化build值
        }
        // for (int i = 0; i < m; i++){
        //     printf("%d", e[i].build);
        // }
        int res = KrusKal(e, m);
        printf("%d\n", res);
    }
    return 0;
}