MST

MST 最小生成树板子

前言

今天对我的图论知识进行了一次的扩充，最小生成树
前言知识：并查集，可以去翻我的博客虽然还不完善但也有一点点的用途

kruskal 算法

思路

kruskal 算法由 kruskal 发明（废话），本质思想是在两个最小联通块之间找到最小的边使得这两联通快之间合并代价最小（就是边权
所以，kruskal 算法是一个贪心的做法
我们按照最小的边权一个一个加入，只要加入不产生环，就把这个点和这个边放进一个点集里
所以，不产生环。。。怎么做呢。。。
并查集咯。
很简单，再加入一条边的时候，就相当联通两个联通块，如果这两个联通块本来就是联合的，加入就会构成一个环
所以只要并查集查找这条边的两个点是不是已经被联通的了就好了
证明就是一个环中删掉最大的边的意思（差不多。。。可以去看 OIWIKI
https://oi-wiki.org/graph/mst/

代码

P3366

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
int fa[maxn];
int n,m;
struct mm
{
    int x,y,z;
    /* data */
}bian[maxn];
bool cmp(mm p,mm q)
{
    return p.z<q.z;
}
int find(int p)
{
    if(fa[p]==p)return p;
    return find(fa[p]);
}
void merge(int p,int q)
{
    p=find(p);q=find(q);
    fa[p]=q;
}
int ans,num;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>bian[i].x>>bian[i].y>>bian[i].z;
    sort(bian+1,bian+1+m,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(find(bian[i].x)!=find(bian[i].y))
        {
            ans+=bian[i].z;
            merge(bian[i].x,bian[i].y);
            if(++num==n-1){
                cout<<ans<<endl;
                return 0;
            }
        }
    }
    cout<<"orz"<<endl;
    return 0;
}

prim 算法：

由于本人不是很会写 prim，经常写的是 kruskal。。。所以就不给放程序这种东西了。。。不过一些思路我还是会的
prim 算法和 kruskal 异曲同工，不过，prim 算法不是加边，而是加点
prim 算法也是维护一个连通块
每次加进去一个距离自己最近的点，加入自己，在更新所有点的距离（重新更新
就像是 dijkstra。。。每次找一个最近的去更新其他的节点距离
所以。。。它也能堆优化
不过就算是堆优化也没有 kruskal 跑的快
所以 建议使用 kruskal

最小生成树的延伸————次小生成树

鸽着