最小生成树的定义：在一个有(n)个点的图中，用(n - 1)条边将其连成一棵树，使得所有(n - 1)条边的权值之和最小。
最小生成树有两种做法：Prim和Kruskal，本文章两个都会介绍。
Prim：
前置知识：堆
Prim的做法就是把点分为已经加入最小生成树的和未被加入的，每次把距离已加入的点最近的边加入最小生成树。不过记录边比较麻烦，我们可以记录点，记(v_i)为节点(i)到已加入部分最短的边的长度，而小根堆记录(v_i)和(i)：
- 首先随便找一个点（一般选1号点）入小根堆。
- 每次取出堆顶(u)并pop。
- 判断(u)是否已经加入最小生成树
- 如果不是，将(v_u)加入最小生成树的边权和
- 然后遍历所有连接的点(x)，
- 若(v_x>v_u)，则将(x)加入堆。
- 重复2,3,4,5,6直到堆为空或者已经加入了(n-1)条边
关于无法形成一个树：该情况就是在结束后判断(n)个点是否都已经被标记，或者由于记录了边的条数，也可以判断边数是否为1。
code:
#include<queue>
#include<cstdio>
#include<cstring>
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_queue<node>q;//小根堆
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()&&cnt<n-1)//cnt记录边的条数，若堆不为空或边数不足n-1则继续
{
int xx=q.top().second;//取出堆顶
q.pop();//弹出
if(!f[xx])//若还未加入最小生成树
{
f[xx]=true;//标记为加入
cnt++;//边数+1
ans+=v[xx];//记录长度
for(int i=g.hd[xx];i;i=g.nxt[i])//遍历能到达的点
if(v[g.to[i]]>g.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的做法：
- 把所有边按顺序排序。
- 从第一条边开始枚举。
- 如果边的两端联通（用并查集判断），就跳过。
- 否则就加入这条边，并合并两个端点的集合。
- 重复3,4步直到枚举完。
关于无法形成一个树：判断是否所有点都在同一个集合里。
code：
#include<cstdio>
#include<algorithm>
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<y.d;}
struct bin
{
int w[5005];
int find(int x)
{
if(x==w[x]) return x;
w[x]=find(w[x]);
return w[x];
}
void add(int x,int y)
{
w[find(x)]=find(y);
return ;
}
bool ask(int x,int y)
{
if(find(x)==find(y)) return true;
else return false;
}
}b;//并查集
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].f,&a[i].t,&a[i].d);
for(int i=1;i<=n;i++) b.w[i]=i;//并查集初始化
sort(a+1,a+m+1,cmp);//按边权排序
for(int i=1;i<=m;i++)//枚举每条边
{
if(b.ask(a[i].f,a[i].t)) continue;//连通则跳过
ans+=a[i].d;//否则记录
b.add(a[i].f,a[i].t);//改为连通
}
for(int i=2;i<=n;i++)
if(!b.ask(1,n))
{
printf("orz");
return 0;
}//判断是否连通
printf("%d",ans);
return 0;
}