题解 | #挖沟#

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;
struct ty{
    int u,w,v;
    bool operator<(const ty x){
        return v < x.v;
    }
}a[maxn];

int n,m,i;
int fa[maxn];

int find(int a)
{
    if(fa[a] == a) 
    {
        return a;
    }
    else
    {
        return fa[a]=find(fa[a]);
    }
}

int join(int a,int b)
{
    if(find(a) != find(b)){
        fa[find(a)]=b;
        return 1;
    }
    
    return 0;
}


int main()
{
    cin >> n >> m;
    for(i=1;i<=n;i++){
        fa[i]=i;
    }
    for(i=1;i<=m;i++){
        cin >> a[i].u >> a[i].w >> a[i].v;
    }
    sort(a+1,a+1+m);
    long long ans=0;
    for(i=1;i<=m;i++)
    {
        if(join(a[i].u,a[i].w)){
            ans+=a[i].v;
        }
    }
    
    cout << ans;
}