题解 | #继续畅通工程#

//还是畅通工程稍微修改即可
#include "bits/stdc++.h"
using namespace std;
int father[5000];
int height[5000];
struct Edge{
    int begin;
    int end;
    int cost;
    int build;
};

void Inti(){
    for (int i = 0; i < 5000; ++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 x_father = Find(x);
    int y_father = Find(y);
    if(height[x_father]>height[y_father]){
     father[y_father] = x_father;
    } else if(height[x_father]<height[y_father]){
        father[x_father] = y_father;
    }else{
        father[y_father] = x_father;
        height[x_father]++;
    }
}

bool compare1(Edge x,Edge y){
    if(x.build != y.build) return x.build>y.build;
    return x.cost<y.cost;
}
int main() {
    int n;
    while (scanf("%d",&n)!=EOF){
        if(n==0){ break;}
        Inti();
        int answer = 0;
        int flag;//1已建
        Edge edge[(n*(n-1))/2];
        for (int i = 0; i < (n*(n-1))/2; ++i) {
            scanf("%d%d%d%d",&edge[i].begin,&edge[i].end,&edge[i].cost,&edge[i].build);
        }
        sort(edge,edge+(n*(n-1))/2,compare1);
        for (int i = 0; i < (n*(n-1))/2; ++i) {
            if(Find(edge[i].begin)!=Find(edge[i].end)){
                Union(edge[i].begin,edge[i].end);
                if(!edge[i].build) answer+=edge[i].cost;
            }
        }
        printf("%d\n",answer);
    }
    return 0;
}