注意只有连通图才有生成树，图不连通就只有生成森林。
最小生成树的板子
Kruskal
基本思想是按边权从小到大加边，是贪心思想。
时间复杂度\(O(m\log m)\)。
板子
sort(e+1,e+tot+1,cmp);
for(int i=1;i<=tot;++i){
int u=e[i].u,v=e[i].v;
u=find(u),v=find(v);
if(u==v) continue;
fa[v]=u;
ans+=g[i].w;
if(--n<2) break;//总共只能加入n-1条边
}
Prim
基本思想是从一个点开始，不断加点。
具体而言，每次找距离已经确定的最小生成树部分最小的点加入最小生成树，并更新其他点到已确定的最小生成树部分的距离。
暴力的时间复杂度为\(O(n^2+m)\)，堆优化的时间复杂度为\(O((n+m)\log n)\)。
暴力板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+10,maxm=2e5+10,inf=1e9+7;
int n,m,tot,ans,head[maxn],dis[maxn];
bool vis[maxn];
struct edge{
int v,w,nxt;
}e[maxm<<1];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) dis[i]=inf;
dis[1]=0;
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
queue<int> q;
q.push(1);
vis[1]=true;
ans=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]) continue;
vis[v]=true;
q.push(v);
ans++;
}
}
if(ans!=n){
puts("orz");
exit(0);
}
ans=0;
for(int i=1;i<=n;++i) vis[i]=false;
for(int i=1;i<=n;++i){
int mini=inf,u=0;
for(int j=1;j<=n;++j){
if(dis[j]<mini&&!vis[j]) mini=dis[j],u=j;
}
ans+=mini;
vis[u]=true;
for(int j=head[u];j;j=e[j].nxt){
int v=e[j].v,w=e[j].w;
if(dis[v]>w) dis[v]=w;
}
}
printf("%d\n",ans);
return 0;
}
堆优化Prim板子
void Prim() {
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push({1,0});
while(!q.empty()){
if(cnt>=n) break;
int u=q.top().u,d=q.top().d;
q.pop();
if(vis[u]) continue;
vis[u]=1;
++cnt;
res+=d;
for (int i=h[u];i;i=e[i].x){
int v=e[i].v,w=e[i].w;
if(w<dis[v]) dis[v]=w,q.push({v,w});
}
}
}
Boruvka
某B开头的神秘MST算法。
在处理完全图上/边有很多特殊性质的MST时，Boruvka的思想很好用（虽然我们一般不会真的去写它）。
主要思想是每次找到每个连通块连上的最小的边，把它加入边集，然后不断重复，直到只有一个连通块。
初始时每个点都被视作独立的联通块。
就酱。
相关的技术
Kruskal重构树
我们在Kruskal的过程中建一棵树出来。
Kruskal从小到大加边，每次加边会合并两个集合，我们新建一个点，点权设为边权，左右儿子设为两个集合的根，然后把两个集合合并，以新建节点为根。
性质
原图上的每个点都是叶子，点权为\(0\)。
原图上两点间所有简单路径上最大边权的最小值=最小生成树上两点间的简单路径上的最大边权=Kruskal重构树上两点LCA的权值。
从一个点\(x\)到根的路径上的点权是单增的。
到点\(x\)的简单路径上最大边权的最小值\(\le val\)的点都在\(x\)到根的链上的某个点的子树内，且为该子树的所有叶子节点，且这个点满足点权\(\le val\)且最浅的。
要是将Kruskal的过程换成从大到小加边，则性质是类似的，“最大的最小”会变成“最小的最大”，其他推一下，其实很一眼。
把重构树建出来后就以解决树上问题的方式做。
标签：int,Kruskal,最小,生成,vis,ans,相关 From： https://www.cnblogs.com/EmilyDavid/p/18623455