# 最小生成树模板

最小生成树有$prime$ 算法和$kruskal$ 算法，本篇暂时贴了克鲁斯卡尔算法写的生成树代码，算法分析请移步另一篇文章

例题：最小生成树

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=5001;
struct node
{
    int a;
    int b;
    int len;
    node(int aa,int bb,int ll)
    {
        a=aa;
        b=bb;
        len=ll;
    }
    node()
    {
    }
    bool operator < (const node & ot) const
    {
        return len<ot.len;
    }
};
int n,m,sum,fa[N],cnt;
vector <node > g;
int find(int f)
{
    if(fa[f]==f)
        return f;
    fa[f]=find(fa[f]);
    return fa[f];
}
void hb(int a,int b)
{
    int f1=find(a),f2=find(b);
    if(f1!=f2)
        fa[f2]=f1;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        g.push_back(node(x,y,z)),sum+=z;
    }
    sort(g.begin(),g.end());
    int ans=0;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=0;i<m;i++)
    {
        if(cnt==m-1)
            break;
        int a=g[i].a,b=g[i].b,len=g[i].len;
        if(find(a)!=find(b))
        {
            hb(a,b);
            cnt++;
            ans+=len;
        }
    }
    printf("%d\n",ans);
    return 0;
 }