题解 | #继续畅通工程#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge{
    int a;
    int b;
    int w;
    Edge(int x,int y,int z): a(x), b(y), w(z){
    };
};

bool compare(Edge a, Edge b){
    return a.w<b.w;
}

const int N = 110;

int p[N];
int h[N];

void init(int n){
    for(int i=1;i<=n;i++){
        p[i]=i;
        h[i]=0;
    }
}

int find(int a){
    if(a!=p[a])p[a]=find(p[a]);
    return p[a];
}

void cunion(int a,int b){
    int x = find(a);
    int y = find(b);
    if(x!=y){
        if(h[x]>h[y]){
            p[y]=x;
        }else if(h[x]<h[y]){
            p[x]=y;
        }else{
            p[x]=y;
            h[y]++;
        }
    }
    return;
}

int kruskal(vector<Edge> edges){
    int ans=0;
    for(int i=0;i<edges.size();i++){
        int a=edges[i].a;
        int b=edges[i].b;
        //cout<<a<<' '<<b<<endl;
        if(find(a)!=find(b)){
            cunion(a, b);
            ans+=edges[i].w;
        }
    }
    return ans;
}


int main() {
    int n;
    while(cin>>n){
        if(!n)break;
        init(n);
        int m = n*(n-1)/2;
        vector<Edge> edges;
        while(m--){
            
            int a,b,w;
            bool st;
            cin>>a>>b>>w>>st;
            //cout<<st<<endl;
            if(st)w=0;
            edges.push_back(Edge(a,b,w));
        }
        sort(edges.begin(),edges.end(),compare);
        
        int ans = kruskal(edges);
        cout<<ans<<endl;
    }
    
}