洛谷P3366【模板】最小生成树（Kruskal）

Kruskal算法的核心：并查集加贪心

思想内容：要让n个点连通，那么至少选n-1条边，又要让各边的长度之和最小，那么只要每次选出最短的边即可，但是注意已经联通的点无须再增加多余的边，这个可以用并查集判断，是否在一个集合内。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;
#define maxn 2000005
#define N 100005
#define ll long long

int n,m,u,v,total;
struct edge{
    int start,to;
    ll val;
}b[maxn];
int f[N];
ll ans;
int find(int x)
{
    if(f[x]==x)return x;
    else{
        f[x]=find(f[x]);
        return f[x];
    }
}
bool cmp(edge a,edge b){
    return a.val<b.val;
}
void kruskal(){
    for(int i=1;i<=m;i++){
        u=find(b[i].start);
        v=find(b[i].to);
        if(u==v)continue;
        ans+=b[i].val;
        f[u]=v;
        total++;
        if(total==n-1)break;
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d %d %lld",&b[i].start,&b[i].to,&b[i].val);
    sort(b+1,b+m+1,cmp);
    kruskal();
    printf("%lld",ans);
    return 0;
}