题解 | #继续畅通工程#

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{
    int x;
    int y;
    int weight;
    int ok;
};
#define N 1000
int father[N];
int height[N];
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){
    x=Find(x);
    y=Find(y);
    if(height[x]<height[y]){
        father[x]=y;
    }
    else if(height[x]>height[y]){
        father[y]=x;
    }
    else{
        father[y]=x;
    }
}
bool cmp(Edge a,Edge b){
    return a.weight<b.weight;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }
        int m=n*(n-1)/2;
        vector<Edge> vec;
        Init(n);
        for(int  i=0;i<m;i++){
            Edge edge;
            scanf("%d%d%d%d",&edge.x,&edge.y,&edge.weight,&edge.ok);
            vec.push_back(edge);
        }
        int tol=0;
        for(int i=0;i<m;i++){
            if(vec[i].ok==1){
                Union(vec[i].x,vec[i].y);
            }
        }

        sort(vec.begin(),vec.end(),cmp);
        for(int i=0;i<m;i++){
            if(vec[i].ok==0&&Find(vec[i].x)!=Find(vec[i].y)){
                Union(vec[i].x,vec[i].y);
                tol=tol+vec[i].weight;
            }
        }

        printf("%d\n",tol);

    }

}