最小生成树

Kruskal 算法

Kruskal 算法不断的从剩余的边中选出一条权值最小的边，并且该边不在生成森林中，将该边加入到生成森林。最开始，每个点独自为一个生成森林，每加入一条边，森林的数量减少一个，加入 $n - 1$ 条边以后，森林变成了最小生成树。

Prim 算法

和 Kruskal 不同，Prim 算法总是维护最小生成树的一部分，找到一个端点属于已确定属于最小生成树的部分，一个端点属于剩余部分，且权值最小的边，将该边加入最小生成树，同时将端点加入已确定最小生成树的部分。

最小生成树的性质

1. 切分性质（Cut Property）

给出图中的所有的点的一个划分 $S$、$T$，所有连接 $S$ 和 $T$ 的边称为这个切分的跨边。如果其中一条边 $e$ 是跨边中权值最小的，那么，一定存在一棵最小生成树包含 e。如果 $e$ 还是严格唯一最小的跨边，那么：所有最小生成树都必须包含 e。

这是 Prim 和 Kruskal 正确性的核心依据。

2. 环性质（Cycle Property）

对于图中的任意一个环，如果某条边 $e$ 是这个环中严格最大的边，那么：

$e$ 不可能出现在任何最小生成树中。

假设 $e$ 出现在某最小生成树里，注意环上至少有一条边不在生成树中，那我们删掉 $e$，将不在生成树中的边加入一条到树中，依然是生成树，但是因为替换掉了最长的边，所以整棵树的权值变小，与原来是最小生成树矛盾。

3. 最小瓶颈性质

定义一棵生成树的瓶颈值为其中最大的边：

$$B(T)=\max_{e\in T}w(e)$$

然后在所有生成树里，让这个瓶颈值尽可能小。最小的瓶颈值对应的树便是最小生成树。

MST 一定是一棵最小瓶颈生成树（MBST）：

$$\boxed{ \max_{e\in MST} w(e) = \min_T\max_{e\in T}w(e) }$$

也就是说，

注意

MST 不仅总权值最小，它的最大边也已经尽可能小。

4. MST 上的路径是 minimax 路径

对于任意两个点 $u,v$，考虑所有 $u\to v$ 路径。

定义一条路径的代价为：

$$\max_{e\in P}w(e)$$

也就是路径上最大的边权。

那么 MST 中 $u\to v$ 的路径满足：

$$\boxed{ \max_{e\in P_T(u,v)}w(e) = \min_{P:u\to v}\max_{e\in P}w(e) }$$

也就是说：

MST 上两点之间的路径，是最大边权最小的路径。

可以表示为

$$\boxed{ \forall e=(u,v)\notin T,\qquad w(e)\ge \max_{f\in P_T(u,v)}w(f) }$$

其中 $T$ 是一棵最小生成树，$P_T(u,v)$ 表示在树 $T$ 中从 $u$ 到 $v$ 的唯一一条路径。

通常称为 minimax path / 最小瓶颈路径。

注意，它不保证：$\sum w(e)$ 最小。

所以：MST 上的路径不一定是最短路。

5. 次小生成树

先求一棵 MST (T)。

枚举一条非树边：

$$e=(u,v)$$

加入以后形成环。

为了尽量小，应该删除这个环上最大的树边。

于是候选生成树权值：

$$\boxed{ W' = W_{\text{MST}} +w(e) - \max_{f\in P_T(u,v)}w(f) }$$

枚举所有非树边即可得到次小生成树。

因此：

提示

MST + LCA 求路径最大边

是次小生成树的经典模型。

MST 中常见的三个动作

切分

最小跨边可以加入 MST。

环

最大边可以尝试删掉

加一条非树边

形成唯一环

例1

题目大意

给定一棵 $N$ 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

暴力做法

设 $u$、$v$ 是树上的两点，考虑到 MST 的性质：MST 上两点之间的路径，是最大边权最小的路径。因此，我们在给 $u、v$ 之间增加边的时候，设 $w$ 是树上 $u、v$ 之间路径的最大值，为了保证唯一的最小生成树是给出的树，且增加的边权最小，那么，增加的边的边权应为 $w + 1$。

由此，我们得到本题的暴力做法： 枚举每一个点对 $(u, v)$，若边 $u\rightarrow v$ 不在树中，则计算路径 $u \sim v$ 中的最大边权 $w$。答案增加 $w + 1$ 即可。

利用倍增 + LCA 可以实现 $O(\log n)$ 的查询路径最大边权。枚举的时间复杂度为 $n^2$。总共的时间复杂度为 $O(n^2\log n)$。

因为每个点对都需要枚举一次，我们可以对每一个点 $s$ 都执行一次 $dfs$。在 $dfs$ 的过程中可以得到 $s$ 到当前节点路径的最大边权。一次 $dfs$ 的时间复杂度为 $O(n)$，我们可以在 $O(n^2)$ 的时间内解决本题。

正解

考虑 Kruskal 算法的求解过程，我们将所有的树边按照从小到达的顺序排列，依次枚举每条边，同时将边所在的两个端点加入同一个连通块。

假设边为 $e=(u, v, w)$。当我们将 $u$ 和 $v$ 用一条长度为 $w$ 的边连接的时候，因为我们是按照从小到大的顺序处理每一条边，那么路径 $u\sim v$ 上的最大边权就是 $w$。设 $x$ 所在连通块为 $A$，$y$ 所在连通块为 $B$，因此，对于 $A$ 和 $B$ 上的点，我们连边，边权最小为 $w + 1$。

此处操作对答案的贡献为 $(|A||B| - 1) \times (w + 1)$。其中 $|A| \cdot |B|$ 表示 $A$ 和 $B$ 之间能连的边数，减 $1$ 是因为需要去掉边 $u\rightarrow v$。

注意到我们的求解步骤恰好就是 Kruskal 算法，这是因为

$$\boxed{\text{Kruskal 的并查集合并过程，本质上是在统计“树上路径最大边”}}$$

例2

题目大意

给定一张 $N$ 个点 $M$ 条边的无向图，求出无向图的一颗最小生成树，满足 $1$ 号节点的度数不超过给定的整数 $S$。$N \le 30$。

法一

提示

先求出保证图连通，$1$ 号节点最少所需连的边，然后尝试给 $1$ 号节点添加边，以获取权值和更小的生成树。

去掉无向图中的 $1$ 号节点，无向图会分成若干个连通块。假设连通块有 $T$ 个。若 $T > S$，则意味着要保证图的连通，$1$ 号节点的度数不能少于 $T$。此时本题无解。

对于每个连通块，在每个连通块的内部求出它的最小生成树。然后从每个连通块中选出一个节点 $p$ 与 $1$ 号节点相连，其中无向边 $(1, p)$ 的权值尽量小。

现在，已经得到了一棵生成树，$1$ 号节点的度数 $T \le S$。现在，我们可以尝试继续给 $1$ 号节点增加 $S - T$ 条边，让答案更优。

枚举 $1$ 号节点不在当前生成树中的每一条边 $(1, x, z)$，然后继续找到当前生成树中从 $x$ 到 $1$ 的路径上权值最大的边 $(u, v, w)$。求出使得 $w - z$ 最大的点 $x_0$。若 $x_0$ 对应的 $w_0 - z_0 > 0$，则从树中删掉边 $(u_0, v_0, w_0)$， 加入边 $(1, x_0, z_0)$。得到的生成树的权值将会变小。

重复上一步 $S - T$ 次，或直到 $w_0 - z_0 \le 0$，就可以得到题目要求的最小生成树。