题解 | 还是畅通工程

#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;
        for(int i=0;i<n*(n-1)/2;i++)
        {
            int a,b;
            cin>>a>>b>>link[i].len;
            if(a>b)swap(a,b);
            link[i].a=a;
            link[i].b=b;
        }
        sort(link,link+n*(n-1)/2, cmp);
        int ans=0;
        for(int i=0;i<n*(n-1)/2;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")