题解 | #继续畅通工程#

//已经建好路的两点间成本改为0
#include <iostream>
#include <algorithm>
using namespace std;

struct Edge{
    int from;
    int to;
    int cost;
    bool operator<(const Edge& e)const{//重载小于号
        return cost<e.cost;
    }
};

Edge edge[5000];
int father[100];
int height[100];


void Initial()
{
    for(int i=0;i<100;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}


int Find(int x)
{
    if(x==father[x])return x;
    else return(Find(father[x]));
}

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;
            height[a]++;
         }
    }
}


int Kruskal(int n,int enumber)
{
    Initial();
    int answer=0;
    for(int i=0;i<enumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from,edge[i].to);
            answer+=edge[i].cost;
        }
    }
    return answer;

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