题解 | #继续畅通工程#

#include <iostream>
#include <algorithm>
using namespace std;


struct Country{
    int from;
    int to;
    int cost;
    int status;
};

const int N=100;

int father[N];
int height[N];

Country country[N*N];


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

int find(int x){//找祖宗节点
    if(father[x]!=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]++;
        }
    }
}

bool comp(Country a,Country b){
    return a.cost<b.cost;
}

int Kruskal(int n,int count){
    initial(n);
    sort(country+1,country+count+1,comp);
    int sum=0;
    for(int i=1;i<=count;i++){
        Country current = country[i];
        if(find(current.from)!=find(current.to)){
            Union(current.from,current.to);
            sum+=current.cost;
    }
}
return sum;
}



int main() {
    int n;
    while(cin>>n){
        if(n==0) break;
        int count=n*(n-1)/2;
        for(int i=1;i<=count;i++){
            cin>>country[i].from>>country[i].to>>country[i].cost>>country[i].status;
            if(country[i].status==1){
                country[i].cost=0;
            }
        }
        int result=Kruskal(n,count);
        cout<<result<<endl;
    }
}

// 64 位输出请用 printf("%lld")