题解 | #继续畅通工程#

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int MAX=100;

struct Edge{
    int from;
    int to;
    int cost;
    bool operator<(const Edge& e)const{
        return cost<e.cost;
    }
};
Edge edge[MAX*MAX];
int father[MAX];
int height[MAX];


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

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

void Union (int x, int y){
    x=Find(x);
    y= Find(y);
    if(x!=y){
        if(height[x]< height[y]){
            father[x]=y;
        }else if(height[y]< height[x]){
            father[y]=x;
        }else{
            father[y]=x;
            height[x]++;
        }
    }
    return;
}

int Kruskal(int n, int edgeNumber){
    Initialize(n);
    sort(edge,edge+edgeNumber);
    int sum=0;
    for(int i=0;i<edgeNumber;i++){
        Edge current =edge[i];
        if(Find(current.from)!= Find(current.to)){
            Union(current.from,current.to);
            sum+=current.cost;
        }
    }
    return sum;
}

int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        if (N == 0) {
            break;
        }
        int edgeNumber = N * (N - 1) / 2;
        for (int i = 0; i < edgeNumber; i++) {
            int status;
            scanf("%d%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost, &status);
            if (status == 1) {
                edge[i].cost = 0;
            }
        }
        int answer = Kruskal(N, edgeNumber);
        printf("%d\n", answer);
    }
    return 0;
}