最小生成树

最小生成树的定义：在一个有\(n\)个点的图中，用\(n - 1\)条边将其连成一棵树，使得所有\(n - 1\)条边的权值之和最小。
最小生成树有两种做法：Prim和Kruskal，本文章两个都会介绍。

Prim：
前置知识：堆
Prim的做法就是把点分为已经加入最小生成树的和未被加入的，每次把距离已加入的点最近的边加入最小生成树。不过记录边比较麻烦，我们可以记录点，记\(v_i\)为节点\(i\)到已加入部分最短的边的长度，而小根堆记录\(v_i\)和\(i\)：

1. 首先随便找一个点（一般选1号点）入小根堆。
2. 每次取出堆顶\(u\)并pop。
3. 判断\(u\)是否已经加入最小生成树
4. 如果不是，将\(v_u\)加入最小生成树的边权和
5. 然后遍历所有连接的点\(x\)，
6. 若\(v_x>v_u\)，则将\(x\)加入堆。
7. 重复2,3,4,5,6直到堆为空或者已经加入了\(n-1\)条边

关于无法形成一个树：该情况就是在结束后判断\(n\)个点是否都已经被标记，或者由于记录了边的条数，也可以判断边数是否为1。

code:

#include
#include
#include
using namespace std;
int n,m,cnt,ans;
int v[5005];
bool f[5005];//f判断该节点是否已经加入最小生成树
struct node
{
    int first,second;
    friend bool operator<(node x,node y){return x.first>y.first;}
};
priority_queueq;//小根堆
struct graph
{
    int tot;
    int hd[5005];
    int nxt[400005],to[400005],dt[400005];
    void add(int u,int v,int w)
    {
        tot++;
        nxt[tot]=hd[u];
        hd[u]=tot;
        to[tot]=v;
        dt[tot]=w;
        return ;
    }
}g;//链式前向星存图
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g.add(u,v,w);
        g.add(v,u,w);
    }
    memset(v,0x3f,sizeof(v));
    q.push((node){0,1});
    v[1]=0;//入堆第一个点
    while(!q.empty()&&cntg.dt[i])//满足条件
                {
                    v[g.to[i]]=g.dt[i];//先更改v
                    q.push((node){v[g.to[i]],g.to[i]});//然后入堆
                }
        }
    }
    for(int i=1;i<=n;i++)
        if(!f[i])
        {
            printf("orz");
            return 0;
        }//判断是否连通
    printf("%d",ans);
    return 0;
}

Kruskal：
前置知识：并查集
Kruskal的做法：

1. 把所有边按顺序排序。
2. 从第一条边开始枚举。
3. 如果边的两端联通（用并查集判断），就跳过。
4. 否则就加入这条边，并合并两个端点的集合。
5. 重复3,4步直到枚举完。

关于无法形成一个树：判断是否所有点都在同一个集合里。

code：

#include
#include
using namespace std;
int n,m,ans;
struct node
{
    int f,t,d;
}a[200005];//存边，Kruskal不用建图
bool cmp(node x,node y){return x.d