题解 | 继续畅通工程

#include <any>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int fa[110];
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
typedef struct Link{
    int a,b;
    int len;

}L;

L link[100010];

bool cmp(L l1,L l2)
{
   
    return l1.len<l2.len;
}

int main() {
    int n;
    while(cin>>n)
    {
        if(n==0)break;
        for(int i=0;i<=n;i++)fa[i]=i;
        int cnt=0;
        for(int i=0;i<n*(n-1)/2;i++)
        {
            int a,b,len,flag;
            cin>>a>>b>>len>>flag;
            if(a>b)swap(a,b);
            if(flag)
            {
                int f1 = find(a);
                int f2 = find(b);
                if(f1!=f2)
                {
                    fa[f2]=f1;
                }
            }else {
                link[cnt].a=a;
                link[cnt].b=b;
                link[cnt].len=len;
                cnt++;
            }
        }
        sort(link,link+cnt, cmp);
        int ans=0;
        for(int i=0;i<cnt;i++)
        {
            int f1 = find(link[i].a);
            int f2 = find(link[i].b);
            if(f1!=f2)
            {
                fa[f2]=f1;
                ans+=link[i].len;

            }
        }
        cout<<ans<<endl;


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