题解 | 继续畅通工程

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int father[1000];
void initalunion(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
    }
    return;
}
int find(int x){
    if(father[x]!=x){
        father[x]=find(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[y]=x;
    }
}
struct edge{
    int u;
    int v;
    int weight;
    int status;
    edge(int _u,int _v,int _weight,int _status){
        u=_u;
        v=_v;
        weight=_weight;
        status=_status;
    }
};
bool compare(edge x,edge y){
    if(x.status!=y.status){
        return x.status>y.status;
    }
    return x.weight<y.weight;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
           break; 
        }
        int u,v,weight,status;
        vector<edge>edgevec;
        initalunion(n+1);
        for(int i=0;i<n*(n-1)/2;i++){
            cin>>u>>v>>weight>>status;
            edge e(u,v,weight,status);
            edgevec.push_back(e);
        }
        sort(edgevec.begin(),edgevec.end(),compare);
        int count=0;
        int edgenum=0;
        for(int i=0;i<edgevec.size();i++){
            int u,v,weight,status;
            u=edgevec[i].u;
            v=edgevec[i].v;
            weight=edgevec[i].weight;
            status=edgevec[i].status;
            if(find(u)!=find(v)){
                Union(u,v);
                if(status==0){
                    count+=weight;
                }
                    ++edgenum;
            }
            if(edgenum==n-1){
                break;
            }
        }
        cout<<count<<endl;
    }
}