最小/最大生成树

给定一张带权无向图 $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(M\log{M})$

#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)\log{N})$

#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 无线通讯网：$S$ 个位置安装卫星电话,$S-1$ 条边是免费的，如果要让 $P$ 个点连通，询问最大的边权。最小生成树上将最大的 $S-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]严格次小生成树

参考代码点击

---

例1. [ABC270F] Transportation

【题意简化】 有 $N$ 座岛，你可以进行下列操作：

在第 $i(1 \le i \le N)$ 座岛上花费 $X_i$ 建一座机场； 在第 $i(1 \le i \le N)$ 座岛上花费 $Y_i$ 建一座海港； 花费 $Z_i(1 \le i \le M)$ 建一座连接第 $A_i$ 座岛和第 $B_i$ 座岛的桥。

如果建了机场的岛都可以互相抵达，建了海港的岛也可以互相抵达，有桥连接的两座岛可以互相抵达，问如果要让这 $N$ 座岛都可以互相直接或间接抵达，最少需要多少花费。

数据范围：$2 \le N \le 2 \times 10^5 ，1 \le M \le 2 \times 10^5 ，1 \le X_i,Y _i ,Z_i \le 10^9$ 。

【分析】为了连接机场、海港，可以创建两个虚拟节点 $n+1$ , $n+2$ 。 所有点与 $n+1$ 连边，边权为岛建机场的费用。如果两个岛要通过机场连接，相当于选择了这两个岛与 $n+1$ 连的边。 同理建海港。

但是这样做，可能会多加入一条边，只有一条机场边，相当于连接了 $n+1$ ,实际没必要。

为了避免这种情况，可以分四种情况，分别跑最小生成树，保留最小值就是答案。

• 1. 只有道路
  2. 道路，和机场，即创建虚拟 $n+1$ 点
  3. 道路，和海港，即创建虚拟 $n+2$ 点
  4. 道路，机场、海港，同时创建虚拟 $n+1,n+2$ 点。

---

学习完毕

{{ select(1) }}

• YES
• NO