【模板】Kruscal+并查集

#include<bits/stdc++.h>
#define MAXN 5005
#define MAXM 200005
using namespace std;
int n,m,f[MAXN],ans=0;
struct Edge
{
    int a,b,c;
    bool operator <(const Edge &temp)const{return c<temp.c;}
}E[MAXM];
int find(int x)
{
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}
int uni(int x,int y)
{
    int fx=find(x),fy=find(y);
    f[fx]=fy;
}
int main()
{
    int x1,x2,x3;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x1,&x2,&x3);
        E[i].a=x1;
        E[i].b=x2;
        E[i].c=x3;
    }
    sort(E+1,E+m+1);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a1=E[i].a,b1=E[i].b;
        if(find(a1)!=find(b1))
        {
            ans+=E[i].c;
            uni(a1,b1);
        }
    }
    printf("%d\n",ans);
    return 0;
}