最小/最大生成树：

给定一张带权无向图$G=(V,E)$，$n$个顶点，$m$条边，取出其中$n-1$条边将$n$个点连通，这个连通图必然是一颗树，这颗树就是图$V$的生成树。

如果取出的这$n-1$条边边权之和最小，那么这颗树就是最小生成树$(Minimum Spanning Tree,MST)$。如果取出的这$n-1$条边边权之和最大，那么这颗树就是最大生成树。

任意一颗最小生成树一定包含图中最小的边。

从原图中取$n-1$条边，若这$n-1$条边不构成环，那必定可以将$n$个点连通，若这$n-1$条边和最小，这$n-1$条边就是最小生成树上的边。

推论： 从原图中取$n-k$条边，这$n-k$不构成环，会生成$k$棵树，也就是生成森林。若这$n-k$条边和最小，也就是最小生成森林。

Kruskal算法和Prim算法都是基于贪心思想的算法，Kruskal算法总是维护无向图的最小生成森林，Prim算法维护最小生成树的一部分，两种算法参考书很多不再详细介绍，具体实现代码参照下面模板：

例1：P3366 【模板】最小生成树

Kruskal算法：时间复杂度$O(MlogM)$

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=2e5+10;
struct node{
	int x,y,z;
}e[M];
int n,m,fa[N];
bool cmp(node a,node b)
{
	return a.z<b.z;
}
int find(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int kruskal()
{
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(e+1,e+m+1,cmp);
	int mst=0;
	int num=0;  //被选中边的数量 
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x);
		int y=find(e[i].y);
		if(x!=y)
		{
			fa[x]=y;
			mst+=e[i].z;
			num++;
			if(num==n-1)return mst; 
		}
	}
	return -1;  //无法构成一颗最小生成树返回-1 
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	
	int ans=kruskal();
	if(ans>0)printf("%d",ans);
	else printf("orz");
	return 0;
}

Prim算法：利用优先队列优化时间复杂度为$O((N+M)logN)$

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=2e5+10;
struct node{
	int to,dis,next;
}edge[M<<1];
int head[N],tot;
int n,m,d[N];
//d[x] 表示点x连入最小生成树集合最小的边
bool vis[N];
void add(int from,int to,int dis)
{
	edge[++tot].to=to,edge[tot].dis=dis;
	edge[tot].next=head[from];
	head[from]=tot;
}
int prim()
{
	int mst=0;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis)); 
	d[1]=0;
	priority_queue<pair<int ,int> >que;
	que.push(make_pair(0,1));
	int num=0; //被确定的点数 
	while(que.size())
	{
		int x=que.top().second;que.pop();
		if(vis[x])continue;
		vis[x]=1;
		mst+=d[x];
		num++;
		if(num==n)return mst;
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,w=edge[i].dis;
			if(d[y]>w)
			{
				d[y]=w;
				que.push(make_pair(-d[y],y));
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	int ans=prim();
	if(ans>0)printf("%d",ans);
	else printf("orz"); 

	return 0;
}

瓶颈生成树：无向图$G$的瓶颈生成树是这样的一个生成树，它的最大的边权值在$G$的所有生成树中最小。 最小生成树必然是瓶颈生成树，反过来不成立。

最小瓶颈路： 无向图$G$中点$x$到点$y$的简单路径上最大边权最小。x 到 y 的最小瓶颈路上的最大边权等于最小生成树上 x 到 y 路径上的最大边权。 但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 x 到 y 的简单路径。

求最小瓶颈路的最大边权，可以在最小生成树上，求点x到y的链上最大边权，可以用二分（判断连通性）、树上倍增、树剖解决。

最小生成树有很多简单入门题，入门题举例如下：

• 1.P2330[SCOI2005]繁忙的都市：求瓶颈生成树，直接求最小生成树。

• 2.P2872[USACO07DEC]Building Roads S：部分边已经连通，可以将连通边边权当做零，再求最小生成树。

• 3.P1396营救：瓶颈路，二分或者树上倍增。

• 4.P2121拆地毯：保留k条边的森林，Kruskal算法从大到小排序，选择k条不构成回路的图。

• 5.P1194买礼物：给定多个连通块，到各个连通块代价已知，可以建立一个虚拟节点，虚拟节点的到各个连通块中的点边权就是统一的代价A元，然后就转化成最小生成树问题了。

• 6.P1195口袋的天空 ：要构成$k$棵树，也就是$k$棵树最小森林，选择$n-k$不构成环的最小的条边。

• 7.P2504[HAOI2006]聪明的猴子：求最小生成树上的最大边权。

• 8.P1991无线通讯网：$P-1$条边是免费的($P$个位置安装卫星电话)，如果要让$n$个点连通，询问最大的边权。最小生成树上将最大的$p-1$边设置成免费，那么不免费的最大的边就是答案。

---

次小生成树与严格次小生成树

先求一颗最小生成树，设边权之和为$sum$，进入最小生成树的$N-1$条边称为“树边”，其他$M-N+1$条边为“非树边”。把一条非树边$(x,y,z)$添加到最小生成树中，会与树上$x,y$之间的路径形成一个环。

设$v_1$是树上$x,y$之间的路径上最大的边权，$v_2$为严格次大边权。

若$z>v_1$，用这条非树边替换这条最大边，得到严格次小生成树一个候选答案，替换后边权之和为$sum-v_1+z$。

若$z=v_1$，替换后权值之和不变，此时次小生成树与最小生成树相同。但是严格次小生成树就必须要用树上$x,y$之间的路径严格次大边替换，用严格次大替换之和边权之和为$sum-v_2+z$。

也就是枚举每条非树边，添加到最小生成树中，计算出“候选答案”，候选答案中的最小值就是严格次小生成树了。问题就转化为如何快速在最小生成树上求一条路径上的最大边权和严格次大边权。

树上一条路径上的最大边权和严格次大边权，可以用树上倍增或树链剖分解决。

设$fa[x][i]$表示$x$的$2^k$辈祖先，$d[x][i][0]$和$d[x][i][1]$表示从$x$到$fa[x][i]$路径上最大边权和严格次大边权。

$fa[x][i]=fa[fa[x][i-1]][i-1]$

$d[x][i][0]=max(d[x][i-1][0],d[fa[x][i-1]][i-1][0])$

分情况计算$d[x][i][1]$

（1）若$d[x][i-1][0]>d[fa[x][i-1]][i-1][0]$

$d[x][i][1]=max(d[x][i-1][1],d[fa[x][i-1]][i-1][0])$

（2）若$d[x][i-1][0]<d[fa[x][i-1]][i-1][0]$

$d[x][i][1]=max(d[x][i-1][0],d[fa[x][i-1]][i-1][1])$

（3）若$d[x][i-1][0]==d[fa[x][i-1]][i-1][0]$

$d[x][i][1]=max(d[x][i-1][1],d[fa[x][i-1]][i-1][1])$

初值：

$fa[x][0]=father[x]$

$d[x][0][0]=edge(x,father[x])$

$d[x][0][1]=-INF$

P4180 [BJWC2010]严格次小生成树 参考代码点击

---

例题：P1967 [NOIP2013 提高组] 货车运输

分析：本题就是询问图中两点间简单路径上最小边权，本质就是最大瓶颈路最小边权，由于有多组询问，二分+判断连通性超时了，转化为最大生成树上两点之间的简单路径上的最小边权，可以用倍增解决。

首先求最大生成树，然后在最大生成树预处理$fa[x][i],d[x][i]$

$fa[x][i]$:表示从$x$往上走$2^i$的祖先$fa[x][i]=fa[fa[x][i-1]][i-1]$

$d[x][i]$:表示从$x$往上走$2^i$到其祖先$fa[x][i]$路径上的最小值 $d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1])$

参考代码：点击

其实本题就是Kruskal重构树的模板题

---

Kruskal重构树

Kruskal重构树能巧妙地求解图中从A点走到B点的所有路径中，最长的边最小值是多少，或者最短的边的最大值之类的问题。

Kruskal算法在加边时，从小到达对边进行排序，被选中的边新产生一个节点，节点的权值就是这条边的边权，同时这个节点作为根，这两个节点的根节点就是新产生节点的左右儿子。

创建Kruskal重构树的核心代码：

void kruskal()
{
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=2*n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x);
		int y=find(e[i].y);
		if(x!=y)
		{
			++num;
			f[x]=f[y]=f[num]=num;
			val[num]=e[i].z;
			add(num,x);
			add(num,y);			
		}
	}
}

Kruskal重构树的本质就是把最小生成树上的边权改成了点权，原图的节点会增加$n-1$个,有性质如下：

• 原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

• kruskal重构树是一颗二叉树，并符合二叉堆的性质。

• 重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

U92652 【模板】kruskal重构树

参考代码：点击

P4768 [NOI2018]归程

分析：首先利用dijkstra求从$1$点到其他点的最短距离，其他点$v$到$1$号点的最短距离，其他点$v$能够坐车的情况下到达一些点，转化为：这些点到$1$号点的最近距离。

然后再按照海拔高度从大到小创建Kruskal重构树，由于Kruskal重构树性质根节点海拔高度最小，也就是整个子树中海拔最低的边权，那么从某个点出发，往上走直到走到海拔高度小于等于限制的节点，以这个节点为根的子树中，点$v$都可以坐车到达，这个子树叶子节点距离起点的最短距离就是答案，可以倍增维护。

参考代码：点击

P4197 Peaks

题意：给定 n 个点 m 条边，每个点有点权（海拔高度），每条边有边权（道路困难程度）。q 组询问，从一个点 v 出发，走边权不超过 x 的第 k 高山峰的高度。

分析：以边权从小到大创建 Kruskal 树，在重构树上从一个点出发，如果朝下走内部点权（原边）变小，也就是都能走，往上走点权变大，当遇到最后一个不超过 x 的点，这个点以下的子树都是从 v 出发能够到达的点。

问题就转变了，在这颗子树内寻找叶子节点第 k 大的问题了。

可以利用 dfs 序，将子树转变为区间，就成了区间第 k 大，可以利用“可持久化线段树”解决。当然要注意 Kruskal 树内部节点并不真实存在，内部点对应的是边，遇到内部点直接复制前一个线段树就好。

参考代码：点击

P4899 [IOI2018] werewolf 狼人

学习完毕

{{ select(1) }}

• YES
• NO