【模板】最小生成树

1.最小生成树是什么

（下面截自百度）

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

自我理解的话就是被最短路后的树（不知道对不对……）

2.最小生成树怎么实现

大体上有两种算法：Kruskal、Prim

这里只解释第一种（第二种之后会补充……猴年马月吧）

大概思路：

大佬思路指路：（CSP-S RP++!）

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    int from,to,v;
    node(){}
    node(int A,int B,int C)
    {
        from=A;
        to=B;
        v=C;
    }
}E[200005];
int n;
int F[50005];
inline bool operator <(const node &a, const node &b){
    return a.v < b.v;
}
int BCJ(int x)
{
    return x==F[x]?x:F[x]=BCJ(F[x]);//超级厉害的一行并查集！！！！ 
}
int tot;
int m;
void add(int x,int y,int z)
{
    E[++tot]=node(x,y,z);
}//存个图吧先
int kruskal()
{
    sort(E+1,E+tot+1);
    for(int i=1;i<=m;i++)
    F[i]=i;//先初始化
    int cnt=m-1;
    int res=0;
    for(int i=1;i<=tot;i++)
    {
        int fx=BCJ(E[i].from);
        int fy=BCJ(E[i].to);
        if(fx!=fy)
        {
            cnt--;
            F[fx]=fy;
            res+=E[i].v;
            if(!cnt)
            return res;
        }

     }
     return -1;
 }
int main()
{
    cin>>m>>n;
    int A,B,C;
    for(int i=1;i<=n;i++)
    {
        cin>>A>>B>>C;
        add(A,B,C);
        //add(B,A,C);
    }
    if(kruskal())
    cout<<kruskal()<<endl;
    else
    cout<<"orz"<<endl;
    return 0;
}

（模板题面点这里）