《寻找第 k 优解的几种方法》阅读笔记

· · 算法·理论

from 余鼎力 2014 年的论文

1 引言

略

2 二分法求第 k 优解

2.1 第 k 优解的定义

首先有最优化问题的数学描述：

定义 2.1. 最优化问题可以认为是在给定的集合上求某函数的极值。对于极小化，即求 \min\limits_{u\in U}J(u)，其中 u 表示问题的解，U 为解 u 所需要满足的给定的约束（称为约束条件），J 即对解的优劣判断的指标（称为目标函数）。

类似的，有第 k 优解的数学描述：

定义 2.2. 第 k 优解问题即在给定集合上求某函数的第 k 极值。对于极小化，即求 \max\limits_{u\in K}J(u)，其中解集 K 满足 |K|=k 且 \max\limits_{u\in K}J(u)\le\min\limits_{v\in U-K}J(v)。

2.2 一个转化

定理 2.1. 第 k 优解问题在只需要求 \max\limits_{u\in K}J(u) 而不需要求解具体方案时，可以花费 O(\log(\sup J(U)-\inf J(U))) 的代价转化为计数问题，其中 J(U) 表示函数 J 在定义域 U 下的值域，且 J(U)\subseteq\mathbb Z.

证明：这里只考虑第 k 小。设集合 S(x)=\{u\in U:J(u)\le x\}，则 \max\limits_{u\in K}J(u)=\min\limits_{|S(x)|\ge k}x。由于 |S(x)| 关于 x 单调，所以可以通过二分求出 \min\limits_{|S(x)|\ge k}x。

由于 J(U)\subseteq\mathbb Z，根据整数二分复杂度，问题可以花费 O(\log(\sup J(U)-\inf J(U))) 的代价转化为：给定 x,U,J，求 \sum\limits_{u\in U,J(u)\le x}1.

第 k 大同理。\square

如果 J(U)\subseteq\mathbb R 且题目要求四舍五入到 d 位小数，那么可以令 J'(u)=\text{round}(J(u)\times 10^d) 使其满足条件。

转化后的计数问题在 u\in U 的基础上添加了一个 J(u)\le x，所以在 J(u) 比较简单时可以考虑直接使用定理 2.1 简化问题，而 J(u) 比较复杂时就可能需要简化 J(u)\le x 这个条件。

2.3 例题一

例 1(COCI 2011/2012 4th round BROJ). 给定质数 p，求最小质因子等于 p 的第 k 小正整数。答案大于 10^9 输出 0.

记 f_x 为 x 的最小质因子，g_x 为 x 的最大质因子，此题中 J(u)=u,U=\{u\in\mathbb Z^+:u\le 10^9,f_u=p\}。容易发现 U=\{vp:v\le\frac{10^9}p,f_v\ge p\}\subseteq\{vp:v\le\frac{10^9}p\}。

$p$ 较小时，可以在 $[1,10^9]$ 中二分 $x$ 并统计 $\sum\limits_{v=1}^{\lfloor\frac xp\rfloor}(1-[f_v<p])=\sum\limits_{d=1}^{\lfloor\frac xp\rfloor}([g_d<p]\mu(d)\lfloor\dfrac x{pd}\rfloor)$。发现 $g_d<p$ 且 $\mu(d)\neq 0$ 的 $d$ 不超过 $2^{\pi(p)}$ 个，所以这部分总复杂度 $O(2^{\pi(p)}\log L)$。 因此总复杂度为 $O(\min\{\frac Lp,2^{\pi(p)}\log L\})$，本题中 $L=10^9$，两种做法分界点取在 $61$ 左右最优。 ## 2.4 例题二 > **例 2**(TopCoder SRM 607 Div.1 - Level 3).桌面上有两个钉子和 $n$ 个滑轮。两个钉子的坐标分别为 $(0,0)$ 和 $((n+1)d,0)$。滑轮半径均为 $r$，圆心坐标为 $(d,0),(2d,0)\dots,(nd,0)$，保证滑轮不重叠。 > > 现在要将两个钉子用一个**紧绷**的绳子连起来，绳子可以在滑轮上绕任意圈。给定 $n,d,r,k$，问所有方案中第 $k$ 短的绳长。要求与答案误差不超过 $10^{-9}$。 > > 数据范围：$1\le r<5\times 10^8,2r+1\le d\le 10^9,1\le n\le 50,1\le k\le 10^{18}$。 首先考虑二分绳长 $mid$，统计绳长不超过 $mid$ 的方案数。 将绳子分成 $e,A,B,R$ 四类，如图： 1. $e$ 表示从一个钉子连到旁边的滑轮的最上方 / 最下方的部分； 2. $A$ 表示从一个滑轮的最上方 / 最下方连到旁边的滑轮的**同侧**部分； 3. $B$ 表示从一个滑轮的最上方 / 最下方连到旁边的滑轮的**异侧**部分； 4. $R$ 表示从一个滑轮的最上方 / 最下方连到自己的异侧部分。 ![pATGhk9.png](https://s21.ax1x.com/2024/12/06/pATGhk9.png) 四类的长度都可以通过简单的几何算出。现在我们需要计算的就是满足 $2e+xA+yB+zR\le mid$ 的符合条件的 $(x,y,z)$ 组数。 考虑设计一个比较暴力的动态规划：用 $(x,y,z,p,d,b)$ 表示当前用了 $x$ 个 $A$，$y$ 个 $B$，$z$ 个 $R$，在第 $p$ 个滑轮上，方向为 $d$（$0$ 表示向右），在轮子上的 $b$ 侧（$0$ 表示上方）的方案数。转移是容易的。 考虑优化。首先，$d$ 完全由 $R$ 的个数 $z$ 决定，可以不记。其次，$b$ 的取值不会影响实际的转移，因为在上方和下方的方案其实是对称的。于是 $A$ 和 $B$ 的转移变得完全相同，所以我们可以在动态规划时只记录 $w=x+y$，在计算方案数时再乘上 $\binom{x+y}{y}$。 因此在统计时可以先枚举 $w,z$ 再枚举 $x$，如果 $2e+xA+yB+zR\le mid$ 就将 $(w,z)$ 方案数乘上 $\binom{x+y}{y}$ 加入答案。因此 $w$ 大概枚举到 $70$ 即可。 但是 $z$ 还是可以很大，继续优化。发现在所有 $A$ 或 $B$ 之后出现的多个 $R$ 没有什么用，因为转两次相当于没转。去掉多余的 $R$ 后可以在最后再乘上一个组合数来分配。于是枚举 $w,z,x(z\le w)$ 后计算最多能加入多少个 $R$，即 $rest=\dfrac{mid-(2e+xA+yB+zR)}{2R}$，将 $(w,z)$ 的方案数乘上 $\binom{x+y}{y}\binom{w+rest+1}{w+1}$ 加入答案。 一些实现细节上的问题：计算 $\binom nm$ 时，如果 $m<4$ 则直接暴力计算，$4\le m\le 70$ 时考虑预处理出 $n\le 70000$ 的所有结果，否则答案一定超过 $10^{18}$。 二分上界可以取 $(n-1)A+2kR$，最终复杂度为 $O(\log^3k\log(dn+rk)+k^{\frac 14}\log k)$。 # 3 整体二分和权值线段树 ## 3.1 整体二分 数据结构题中经常会要求回答多组询问，例如询问区间第 $k$ 极值。我们仍然可以二分，但是单纯的二分是不够的，所以使用 **整体二分**。它需要的性质： 1. 答案具有可二分性； 2. 修改对判定答案的贡献互相独立且修改之间互不影响； 3. 修改如果对判定答案有贡献则贡献应该确定且与判定标准无关； 4. 贡献满足交换律、结合律，具有可加性； 5. 题目允许离线。 其中在求第 $k$ 优解时第一条已经被定理 2.1 证明。 ## 3.2 权值线段树求第 $k$ 优解 整体二分需要满足的性质中，第二条和第五条非常苛刻，因为很多问题都需要在线进行而且会有修改单点权值。这种情况下，我们可以使用 **权值线段树** 将问题转化为计数问题，同样花费 $O(\log W)$ 的代价。 建立出权值线段树，询问时直接在权值线段树上二分，插入一个新的解时直接插入到权值线段树上。修改一个解就是先删除再插入。 这种方法的问题是无法修改 $u\in U_j$ 的所有 $J(u)$，即一个操作变化时无法修改所有变化的解。 可以发现整体二分时也是在利用这种模型，但是整体二分是离线地在权值线段树上遍历而不维护数据结构，所以无法支持可能会产生影响的修改，但好处是它可以继续在线段树节点上套用分治等离线算法。 ## 3.3 例题三 > **例 3**(BZOJ 3065 带插入区间 k 小值).给定一个序列，你需要支持三种操作：查询区间第 $k$ 小；单点修改；单点插入。强制在线。 > > 数据范围：$1\le n\le 35000$，总插入个数 $\le 35000$，总修改个数 $\le 70000$，询问个数 $\le 70000$，所有权值在 $[0,70000]$ 之间。 维护权值线段树，每个节点是一棵平衡树 $T_{l,r}$，按照原序列顺序维护权值在区间 $[l,r]$ 内的数。如果一个数权值 $\le m=\lfloor\frac{l+r}2\rfloor$ 那么它在平衡树中的特征值为 $0$，否则为 $1$。 询问时先找到 $x$ 和 $y$ 在根节点的平衡树中特征值为 $0$ 的数的个数 $s$，如果不超过 $k$ 就递归到左子树，否则递归到右子树并令 $k$ 减去 $s$。递归到叶子结点即可。插入和修改方法类似。 总复杂度 $O((n+q)\log W\log n)$，代码难度比其他复杂度相同的算法要低。 ## 3.4 权值线段树的另一种用法 如果换一个思路将权值线段树作为某一数据结构中的点以维护区间中解的权值分布情况，会产生一个问题：很多数据结构需要合并点权，而权值线段树无法高效合并。 对于答案的合并，由于只需要询问第 $k$ 极值，所以我们可以假设已经合并好了并得到了答案对应的权值线段树。在答案的树上二分的时候再计算当前需要统计的节点的值。 对于标记也是权值线段树的情况，因为无法下传标记，所以应标记永久化。详见例 4。 对于数据结构中需要用子节点更新父节点的情况，如平衡树左右旋，可以考虑选择重量平衡的数据结构，如 Treap，替罪羊树，暴力重构子树做到期望或均摊较优的复杂度。 ## 3.5 例题四 > **例 4**(ZJOI2013 K 大数查询).有 $n$ 个可重集和若干次操作，操作有两种：给一个区间的可重集添加一个数 $c$，或者查询区间可重集的并的第 $k$ 大。 > > 数据范围：$n,m\le5\times10^4$。 对于每个位置维护一棵线段树，线段树上每个节点维护两棵权值线段树：一棵为 $C_{l,r}$ 表示当前节点的标记，表示当前线段树区间内每个可重集都添加了这些数；另一棵为 $T_{l,r}$ 维护当前线段树区间内所有数的权值。 对于询问操作，如果 $a=l$ 且 $b=r$ 那么直接返回 $T_{l,r}$，否则返回递归到左右儿子的结果加上 $C_{l,r}(b-a+1)$。 对于修改操作，在 $T_{l,r}$ 中加入 $(b-a+1)$ 个 $c$，如果 $a=l$ 且 $b=r$ 就在 $C_{l,r}$ 中加入 $c$，否则递归下去。 总时间复杂度 $O(m\log^2n)$。 这个做法还可以再花费 $O(\log n)$ 的代价来支持区间所有数加一个值。在线段树上多维护一个标记 $D$ 表示当前节点对应区间全都加了 $D$。修改时进入节点就要先减去当前节点的 $D$。询问时由于答案是 $\sum s(T+d)$ 的形式，其中 $T$ 是一棵权值线段树，所以最后在权值线段树上走的时候会多付出 $O(\log n)$ 的代价，总复杂度 $O(m\log^3n)$。 # 4 字典树上的统计 有一类题目求满足条件的字典序第 $k$ 小的字符串。这类问题可以硬套二分，但是这样会使问题变得更复杂，所以不如考虑从前往后逐位确定。 逐位确定的实质就是在字典树上走，保持当前子树所有满足条件的方案数不小于 $k$。每次按照字典序尝试走向每一个儿子，假设当前儿子方案数为 $s$，如果 $s\ge k$ 则直接走到该儿子，否则 $k\gets k-s$。而某一节点子树内满足条件的字符串个数等价于求以某个串为前缀的满足条件的字符串个数。 不仅是字符串，求第 $k$ 小排列等也是用这种方法。 ## 4.1 例题五 > **例 5**. 给定一个字符串 $s$，求第 $k$ 小子串。两个子串的起始位置和结束位置不同就视为不同子串。 > > 数据范围：$|s|\le 10^5$。 建出 $s$ 的后缀树，后缀树也是字典树的一种，所以可以在后缀树上走得到答案。在后缀树上某一子树内求子串个数可以通过树形 dp 求出。 本题其他做法的本质也是在后缀树上走。 ## 4.2 例题六 > **例 6**. 对于一个包含 $W$ 个单词的语句，相邻两个单词之间用一个空格隔开，单词只包含小写字母，其信息量为所有字符的信息量之和。空格信息量为 $1$，`a` 信息量为 $2$，以此类推，`z` 信息量为 $27$。问信息量为 $V$ 的字典序第 $k$ 小的语句。 > > 数据范围：$1\le V\le 1000,1\le W\le 300,1\le k\le 10^{18}$。 可以直接套用前面所说的在字典树上走并询问以某个串为前缀的所有满足条件的字符串个数。 每次暴力动态规划无法通过，所以提前预处理出方案数，总复杂度 $O(VW)$。 # 5 优先队列在第 $k$ 优解中的应用 ## 5.1 一个使用堆的例子 首先引用一道算法导论中的习题： > **例 7**(Introduction to Algorithms 6.5-8). 请给出一个时间为 $O(n\log m)$、用来将 $m$ 个已排序的链表合并为一个排序链表的算法。此处 $n$ 为所有链表元素总数。 做法十分显然。首先将 $m$ 个链表头放入一个小根堆。进行 $n$ 次操作，每次取出堆中最小的节点接在答案链表最后，并把其在原链表中的下一个加入堆中。 > **例 8**. 给出两个序列 $a$ 和 $b$，求出 $a_i+b_j$ 的第 $k$ 小值。 > > 数据范围：$n,m,k\le 5\times 10^5$。 将 $b$ 排序并设 $c_{i,j}=a_i+b_j$，那么 $c_1,\dots,c_n$ 均为长为 $m$ 的有序表。按照例 7 的做法执行 $k$ 次即可获得前 $k$ 小值。时间复杂度 $O(m\log m+k\log n)$。 当然本题也可以通过二分答案+双指针解决，复杂度 $O(n\log W)$，但是二分仅能求出第 $k$ 小而无法得到前 $k$ 小。 ## 5.2 使用优先队列求第 $k$ 优解的一般方法 构造解的一张图 $P$ 满足每个解都是图中的一个或多个点，每个点都是一个合法解，且这张图满足堆的性质：如果 $u$ 连向 $v$，则 $J(u)\le J(v)$。 建立一个权值为 $-\infty$ 的超级源点 $S$ 连向所有没有入度的点，那么从 $S$ 出发能到达所有解。 用一个优先队列维护已扩展的点，最初只有 $S$ 一个点，进行 $k+1$ 次操作，每次弹出当前优先队列中的最优解，将所有能扩展到且还没被遍历到的点都加入优先队列。注意图不需要提前建出，可以在需要的时候再建边。判断是否被遍历过可以用哈希表等。此时如果遍历过 $state$ 个点那么总复杂度 $O(state\log k)$。 注意到图的堆性质，可以考虑给边添加边权，$c(u,v)=J(v)-J(u)$。在边有权值的情况下，可以扩展图 $P$ 的定义：从 $S$开始的路径与问题的解**一一对应**，解的值为路径上的边权和。此时图 $P$ 不一定是拓扑图（可能有相等情况）。 另外，例 8 还有一个 $O(k\log k+n+m)$ 的做法：先对 $b$ 建小根堆（可以 $O(m)$ 建出），堆中父亲向儿子连边边权为权值差；$S$ 向堆根连 $n$ 条边，边权为 $a_i+\min b$。 这样对于 $S$ 可以只加入边权前 $k$ 小，总复杂度 $O(k\log k+n+m)$，图 $P$ 见下。 ![pATtMo4.png](https://s21.ax1x.com/2024/12/06/pATtMo4.png) 之后的章节中我们将看到优先队列求第 $k$ 优解时的应用以及更多构建 $P$ 的巧妙方法。 # 6 $k$ 短路算法 > **定理 6.1.** 在一张有向带权图 $G$ 中，从起点 $s$ 到终点 $t$ 的可重复经过同一点的不严格递增的第 $k$ 短路长度可以在 $O(n\log n+m+k\log k)$ 的复杂度内得到。 **证明**：对于一条边 $e$，记他的长度为 $l(e)$，起始点为 $hd(e)$，终止点为 $tl(e)$，$d(u,v)$ 表示 $u$ 到 $v$ 的最短距离。 ## 6.1 问题转化 定义 $T$ 为 $G$ 中以 $t$ 为终点的最短路径构成的最短路树。对于一条边 $e\in G$，定义 $\delta(e)=l(e)+d(tl(e),t)-d(hd(e),t)$，则有 $\forall e\in G,\delta(e)\ge 0;\forall e\in T,\delta(e)=0$。 将 $T$ 严格定义为一棵树：对于一个节点 $v\neq t$，定义 $nxt_T(v)$ 为 $v\to t$ 的最短路径（不唯一则任选一条）上 $v$ 的后继节点，那么 $G$ 中所有点就以 $nxt_T$ 形成一个严格的树结构 $T$。 对于一条 $s\to t$ 的路径 $p$，去掉 $p$ 中所有在 $T$ 中的边，定义为 $st(p)$。 $st$ 有三条性质： > **性质 6.1.** 对于 $st(p)$ 中任意一条边 $e$，有 $e\in G-T$；对于 $st(p)$ 中任意相邻两条边 $e,f$，都满足 $hd(f)$ 是 $tl(e)$ 在 $T$ 树上的祖先或 $hd(f)=tl(e)$。 > **性质 6.2.** $p$ 的路径长度 $L(p)=d(s,t)+\sum\limits_{e\in st(p)}\delta(e)=d(s,t)+\sum\limits_{e\in p}\delta(e)$。 > **性质 6.3.** 对于一个满足性质 6.1 的边的序列 $q$，有且仅有一条 $s\to t$ 的路径 $p$ 满足 $st(p)=q$。 这三条性质比较显然。于是我们的问题就变为求第 $k$ 小的满足性质 6.1 的边的序列。 即序列中任意一条边 $e$ 都有 $e\in G-T$；相邻的两条边 $e,f$ 都满足 $hd(f)$ 是 $tl(e)$ 在 $T$ 上的祖先或者相等。 序列 $q$ 的权值定义为 $\sum\limits_{e\in q}\delta(e)$。 ## 6.2 构建 $P

算法一 初始解为空序列。对于一个序列 q，令其最后一条边的 tl 为 v（若是空序列则 v=s）。在 q 中加入一条边 e 得到新序列 q'（hd(e) 在 T 中 v\to t 的路径上且 e\in G-T）。q 向 q' 连边权为 \delta(e) 的边。如下图。

这样的图 P，每个点出度至多为 m，总复杂度为 O(n\log n+km(\log k+\log m))。

算法二 上图可以对每个点的所有边权排序，然后用左儿子右兄弟的方法将出度减少至 2，兄弟之间的边权为两者之差。它的意义在于建立一张有序表 g(v)，按权值从小到大记录所有在 G-T 中且 hd(e) 在 T 中 v\to t 的路径上的边 e。

对于序列 q，令其最后一条边为 e，v=tl(e)，倒数第二条边的 tl 为 u。将 e 替换为 g(u) 中 e 的后一条边或者在 q 中新加入 g(v) 中的第一条边得到新序列 q'。如下图。

复杂度 O(n\log n+nm\log m+k\log k)。

算法三 上一个算法瓶颈在于对每个点都建立有序表。注意到 g(v) 和 g(nxt_T(v)) 大部分相同，因为我们是在 g(nxt_T(v)) 中添加所有在 G-T 中由 v 连出去的边来得到 g(v) 的，但是因为有序表的添加复杂度，我们无法快速求得 g。

如果我们对于点 v 不建立 g(v) 而建立一个堆 H(v)（类似例 8 的 O(k\log k+n+m) 做法）并通过在 H(nxt_T(v)) 中可持久的加入所有在 G-T 中由 v 连出去的边来得到 H(v)，就可以解决上面所有的问题。

这里需要可持久化的原因是我们一直需要使用插入前的堆。而对于上一算法中将 e 替换为 g(u) 中 e 的后一条边，我们直接用 e 在 H(u) 中的儿子替换 e 即可。

复杂度 O(n\log n+m\log m+k\log k)。

算法四 例 8 的 O(k\log k+n+m) 做法中，我们用到了建堆的优越性，这里我们也可以利用。

对于点 v 用堆 h(v) 维护所有在 G-T 中由 v 连出去的边，并将 h(v) 中最小元素的权值作为 h(v) 的权值。于是把 h(v) 当做一个节点，可持久的插入 H(nxt_T(v)) 得到堆的堆 H(v)。

于是建 h(v) 时间为 O(m)，建 H(v) 时间减少为 O(n\log n)，所以总复杂度 O(n\log n+m+k\log k)。\square

7 一类动态规划问题

拓扑图的最短路可以通过动态规划实现。反过来，若某一动态规划能转成拓扑图且它构出的图的边 (a,b) 意义为 b\le a+l(a,b)，其中 a 和 b 都对应一个状态，状态转移方程对应为 b=\min(b,a+l(a,b))，那么此时动态规划的最优解可以用最短路求解。

定理 7.1. 若某一动态规划能转成拓扑图且它构出的图的边 (a,b) 意义为 b\le a+l(a,b)，其中 a 和 b 都对应一个状态，状态转移方程对应为 b=\min(b,a+l(a,b))，且此动态规划的所有决策方案与拓扑图中所有起始点到终止点的路径一一对应，那么此动态规划的第 k 优解可以用 k 短路实现。

证明：由于动态规划时初始状态和终止状态不一定唯一，所以需要新建节点 s,t，s 向所有初始点连长度为 0 的边，所有终止点向 t 连长度为 0 的边，此时动态规划第 k 优解即为 s\to t 的 k 短路。\square

如果转移方程是 \max 的形式，则对所有边权都取相反数，最后答案也取相反数即可。

7.1 例题九

例 9. 给出 n 个数轴上的点 x_i，将它们划分为两个集合 S_A,S_B。对于一个集合 S=\{p_1,p_2,\dots,p_{|S|}\}，其中 p 递增，这个集合的代价 l(S)=\sum\limits_{k=0}^{|S|-1}|x_{p_k}-x_{p_{k+1}}|，默认 x_{p_0}=0。求所有方案中第 k 小的 l(S_A)+l(S_B)。

数据范围：n\le 10^4,k\le 5\times 10^5。

解法一

如果 k=1，则可以设计动态规划解决这个问题。记 f(i,j) 表示两个集合末尾分别为 i 和 j 时的最小代价（默认 i\ge j）。转移时枚举 i+1 放到哪边，即 f(i+1,j)\gets f(i,j)+|x_{i+1}-x_i|,f(i+1,i)\gets f(i,j)+|x_{i+1}-x_j|。初始化 f(0,0)=0，其他均为 \infty，答案为 \min\limits_{j<n}f(n,j)。

此时如果直接建拓扑图求 k 短路，因为点数和边数均为 O(n^2)，总复杂度 O(n^2\log n+k\log k)。

容易发现 f(i+1,j)-f(i,j) 只有 j=i 时不确定，其他时候值都为 |x_{i+1}-x_i|。而 f(i+1,i)=\min\{f(i,j)+|x_{i+1}-x_j|-|x_{i+1}-x_i| \}+|x_{i+1}-x_i|。

如果求出 M_{i+1}=\min(f(i,j)+|x_{i+1}-x_j|)，就可以 f(i,i)\gets M_{i+1}-|x_{i+1}-x_i|，然后将整个 f(i) 加上 |x_{i+1}-x_i| 得到 f(i+1)。

这样点数变为 O(n) 且仍然满足所有条件，复杂度变为 O(n\log n+n^2+k\log k)。

解法二

求 M_i 可以使用线段树优化，这样每次线段树中只会新建 O(\log n) 个节点（需要离散化），边数也优化至 O(n\log n)，复杂度 O(n\log^2n+k\log k)。

考虑修改线段树的结构，改成一个 d 等分的形式。这样修改时点数会减少至 O(\log_dn)，询问时区间个数变为 O(d\log_dn)，总复杂度 O(\dfrac{n\log^2n}{\log d}+\dfrac{nd\log n}{\log d}+k\log k)，取 d=\log n 即可变为 O(\dfrac{n\log^2n}{n\log\log n}+k\log k)。

8 k 小生成树

8.1 最小生成树

Prim 和 Kruskal 是大家常用的最小生成树做法，复杂度 O(n\log n+m) 和 O(m\log n+m\alpha(n))。

也有一些比两者更优的算法可以做到期望线性，或最坏 O(m\alpha(m,n))。

8.2 次小生成树

典题，步骤如下：

也就是说，选择一条非树边去替换掉一条树边使其仍是生成树，次小生成树一定在这些之中。maxw(u,v) 可以倍增求出，总复杂度 O(m\log n)。

8.3 k 小生成树

先给出一个 O(m\log n+k^2) 的做法。（9 连引理警告）

下面用 ST 表示生成树，MST 表示最小生成树。

8.3.1 收缩必要边

对于一张无向图 G 和其上一条边 e=(x,y)，定义收缩图 G\cdot e 为点集为 V(G)-y，边集为 c_e(E(G)) 的图，其中 c_e 表示去掉所有 (x,y) 边并把所有 (y,z) 和 (x,z)。

引理 8.1. T 为 G 的一棵 ST，e 为 T 上任意一条边，c_e(T) 是 G\cdot e 的 MST 当且仅当 T 是 G 的最小的包含 e 的 ST。

证明：直接由定义可以得出。\square

引理 8.2. v 为 G 中一点，e 为所有与 v 相连的边中最小的一条。令 T 为 G\cdot e 的 MST，那么 T+e 为 G 的 MST。

证明：令 e=(u,v)，若 e 不在 G 的 MST 中则 v\to u 必然有路径，设其与 v 相连的边为 f，那么 l(f)\ge l(e)，由于将 f 换成 e 后仍为 ST，所以 e 必然在 G 的一棵 MST 中。由引理 8.1，T+e 为 G 的最小的包含 e 的 ST，所以 T+e 不大于 G 的 MST，所以 T+e 是 G 的 MST。\square

对于一条 ST 上的边 e，它将 ST 分为 T_1,T_2，定义 r_G(e) 为除 e 以外最小的跨越 T_1 和 T_2 的边。

引理 8.3. 对于任意一条 MST T 上的边 e，如果 G-e 连通那么 T-e+r_G(e) 是 G-e 的 MST。

证明：可以通过对点数进行数学归纳法得出，每次收缩一个叶子。\square

引理 8.4. 给出 G 的 MST T，所有 T 上的边 e 的 r_G(e) 能在 O(m\log n) 的时间复杂度内得到。

证明：枚举所有非树边 e=(u,v) 并在树上对应路径上覆盖 e，最后求每条树边上被覆盖的最小非树边即可。可以动态树或者排序后并查集等方法。\square

引理 8.5. 给出 G 的 MST 和所有树边的 r_G，可以在线性时间内算出 n-k 条一定在 k 小 ST 中的边。

证明：对于一条树边 e，令 l'(e)=l(r_G(e))-l(e)，即删除这条边对 MST 的额外代价。然后我们可以 O(n) 获得前 k-1 小的 l'，设其余树边集合为 S。对于 S 中任意一个 e，至少存在 k-1 个 e' 满足 l(T-e'+r_G(e'))\le l(T-e+r_G(e))，也就是至少有 k 棵 ST 大小不劣于 l(T-e+r_G(e))。根据引理 8.3，至少有 k 棵 ST 大小不劣于任意一棵不包含 e 的 ST ，因此 e 一定在 k 小 ST 中。\square

引理 8.6. 给出 G 的 MST T，在 O(m\log n) 的时间内可以找到一个边集 S 和一张 k 个点的图 G'，使得 G 的 k 小 ST 恰好为 G' 的 k 小 ST 加上 S。

证明：令 S 为引理 8.5 中的边集，令 G'=G\cdot S，即收缩所有 S 中的边。\square

8.3.2 去掉无用边

与 r_G(e) 类似，对树边 e=(u,v)，定义 R_G(e) 为树上 u\to v 路径上的最大边。

引理 8.7. 若 T 是 G 的 MST，那么 c_e(T-R_G(e)) 为 G\cdot e 的 MST。

证明：对点数进行数学归纳，每次收缩一条非 R_G(e) 的树边，由引理 8.1 可得。\square

引理 8.8. 给出 G 的 MST T，所有非树边 e 的 R_G(e) 可以 O(m\log n) 求出。

证明：即求树上路径最大值，可以倍增 O(m\log n) 得到。\square

引理 8.9. 给出 G 的 MST 和所有非树边的 R_G(e)，可以线性求出 m-n-k 条一定不在 k 小 ST 的非树边。

证明：定义 L(e)=l(e)-l(R_G(e))，那么令 f 为所有非树边中 L 第 k-1 小的边。那么对于一条边 e，若 L(e)>L(f) 则至少有 k 棵 ST 的大小不超过 T-R_G(e)+e 即不超过任意包含 e 的 ST，则 e 一定不在 G 的 k 小 ST 中。\square

这样，我们就将 n 减小至 k，m 减小至 2k-2。之后默认 n\le k，m\le 2k-2。

对于 k=2 的情况，n,m 均减少至 2，所以之前次小生成树的做法正确性可直接推得。

8.3.3 构建 P

定义 P 中一个节点为 R，由三部分组成：ST T，一定在 ST 中的边集 I，一定不在 ST 中的边集 X。

首先考虑最朴素的构建 P 的方法。起始点 S=R_1=(T_1,\varnothing,\varnothing)，T_1 为 G 的 MST。

对于一个 R_i=(T_i,I_i,X_i)，枚举下一次替换的边 e\in T_i-I_i，T 变为 T_i-e+r_{G-X_i}(e)。对这些替换按长度排序，设排序后被替换的边为 e_1,e_2,\dots 那么 R_i 扩展出节点 (T_i-e_j+r_{G-X_i}(e_j),I_i+\sum\limits_{k<j}e_k,X_i+e_j)。

根据 P 的定义，需要证明所有 R_i 与所有可行 ST 一一对应且图满足堆性质。

先证明所有 R 与所有可行 ST 一一对应。

证明：令 R 对应其定义中的 ST T，只需要证明一棵 ST 只有一个 R 与之对应。

先证明一棵 ST T 至少存在一个 R 与之对应：设 R_i 为当前 ST，满足 I_i\subseteq T 且 X_i\cap T=\varnothing。最初 i=1，即 R_i=R_1=(T_1,\varnothing,\varnothing)，满足条件。如果 T=T_i 则我们就找到了 R_i 与 T 对应，否则由于 T\neq T_i 所以 R_i 中至少有一个儿子 R_j 满足条件，于是将 R_i 变为 R_j 继续即可。因为 |I_i|+|X_i| 每次至少增加 1，所以这个过程不会无限进行，因此一定能找到与 T 对应的 R。

再证明一棵 ST T 不会对应多个 R，即每个 R 对应的 T 互不相同：设一个节点 R 的儿子按顺序分别为 R_1,R_2,\dots 那么由于 X_i=X+e_i 且 e_i\in T，所以 T 与 R_i 及其子树内所有点对应 ST 均不相同。对于节点 R_i,R_j，设 i<j，则 e_i\in X_i,e_i\in I_j，所以 R_i 及其子树内所有 ST 与 R_j 及其子树内所有 ST 互不相同。对 |I_i|+|X_i| 进行数学归纳，可以得出以 R 为根的子树内所有节点 ST 互不相同。\square

再证明图满足堆性质：

证明：对于 I_i 中所有边，视其边权为 -\infty；对于 X_i 中所有边，视其边权位 +\infty。那么对于 P 中节点 R，满足 T 是改边权后图的 MST。

可以通过数学归纳证明，首先 R_1 满足。考虑若 R_i 满足，那么对于 I_i+\sum\limits_{k<j}e_k，T_i-e_j+r_G(e_j) 为次小 ST，所以对于 I_i+\sum\limits_{k<j}e_k,X_i+e_j，T_i-e_j+r_G(e_j) 为 MST，所以 R_j 满足。

而随着 I 增大，MST 不会变优，而 X 增大会使 MST 变劣，因此图 P 满足堆性质。\square

接下来考虑类似前面的优化方法，使用左儿子右兄弟的方法减少单个点的出度。

8.3.4 算法流程

首先求出 MST，设为 T_1。令 R_1=(T_1,\varnothing,\varnothing)。如下图，实线为 MST，虚线为非树边。

假设现在已经求出前 k 优解：R_1\sim R_k。找一个最小的替换 (i,e,f) 使 T_i-e+f 仍然是一棵树且 l(T_i-e+f) 是所有替换中最小的，e\notin I_i 且 f\notin X_i。

那么 R_{k+1}=(T_i-e+f,I_i,X_i+e)，并将 R_i 改为 (T_i,I_i+e,X_i)。如下图，将 (c,f) 换为 (i,g)，那么 T_2 中 (c,f) 就在 X 中无法再出现在树上，T_1 中 (c,f) 强制在树上，用两条线表示。

接下来，我们把 T_1 中的 (b,c) 换成 (b,h) 得到 T_3。再接下来，我们把 T_1 中的 (g,f) 换成 (i,g) 得到 T_4。

现在问题是如何快速得到最小替换。有两种方法：

  1. 维护所有树边的 r_G。暴力维护是 O(km\log n)，可以提前排序将其优化至 O(km\alpha(n))。
  2. 维护所有树边的 R_G。暴力维护是 O(km\log n)，可以优化至 O(km)。
把 $e$ 换成 $f$ 并在 $X$ 加入 $e$ 的做法如下： 设 $e=(u_0,v_0)$，去掉 $e$，树分成 $T_1,T_2$，设 $u_0$ 在 $T_1$ 中，$v_0$ 在 $T_2$ 中。设 $T_1$ 中 $u_0\to f$ 的路径为 $u_0\sim u_p$，$T_2$ 中 $v_0\to f$ 的路径为 $v_0\sim v_q$，其中 $f=(u_p,v_q)$。 如果将 $e$ 换成 $f$ 那么只有横跨 $T_1,T_2$ 的非树边在树上的路径会改变。具体的，横跨 $T_1,T_2$ 的非树边在树上的路径会异或整个环 $u_0\to u_1\to\dots\to u_p\to v_q\to\dots\to v_q\to v_0\to u_0$。因此只需要更改所有横跨 $T_1,T_2$ 的非树边的 $R_G$。 对树进行一次遍历，求每个点距离它最近的环上的点。对于一条非树边 $e=(u,v)$，设距离 $u,v$ 最近的环上的点分别为 $u',v'$，则 $R_G(e)$ 由五部分构成：$u\to u',u'\to u_p,f,u_q\to v',v'\to v$。这些都可以通过维护前缀信息在 $O(n+m)$ 时间得到。复杂度为 $O(km)$。 于是回到原问题，总复杂度 $O(m\log n+k^2)$。 # 9 $k$ 小简单路径 $k$ 小简单路径是求在一张有向带权图 $G$ 中 $s\to t$ 的**不**可重复经过同一点的不严格递增的第 $k$ 短路。下面默认 $G$ 不包含负环。 虽然它与 $k$ 短路的定义只相差一个“不”字，但求解 $k$ 小简单路径与求解 $k$ 短路的方法相差很大，反而与 $k$ 小生成树解法类似。 ## 9.1 构建 $P

分析之前 k 小生成树的构造，P 是一棵树，P 中节点 v 始终优于其子树内的点。

类似的，可以构建 k 小简单路径图 P：

现在问题在于如何将一个集合进行划分使得划分后的集合最优解容易求出。在 k 小生成树中，我们强制包含和强制排除一些边，在求 k 小简单路径时也是类似的：

令图 P 中一个节点 R 由三部分组成：当前简单路径 p，强制包含的边集 I，强制不包含的边集 X。其中令 p=(v_1=s,\dots,v_{|p|}=t)，保证 I=\{(s,v2),(v2,v3),\dots,(v_{q-1},v_q)\} 且 q\le|p|-1，X 中全是从 v_q 出发的边。

但是我们无法像 $k$ 小生成树一样使用左儿子右兄弟的方法减少单个节点的出度，因为我们无法快速判断兄弟之间的大小关系。 ## 9.2 算法流程 求出 $s$ 到其他点的最短路，将 $(u,v)$ 的边权换为 $l(u,v)+dis(s,u)-dis(s,v)$。类似于原来 $k$ 短路算法中的 $\delta$。此时 $s\to t$ 的任意一条路径长度需要加上原先 $s\to t$ 的最短路。将 $(s\to t,\varnothing,\varnothing)$ 加入优先队列。 每次从优先队列中弹出最小的点 $R=(p,I,X)$，并将它能扩展出的 $R_i=(p_i,I_i,X_i)$ 全都加入优先队列。 符合条件 $I_i,X_i$ 的最短路径 $p_i$ 可以通过 Dijkstra 在 $O(n\log n+m)$ 复杂度内得到。由于 $k$ 个点最多扩展出 $kn$ 个点，所以需要计算 $kn$ 次最短路，总复杂度 $O(kn(m+n\log n))$。 # 10 感谢 感谢大家阅读，写了五个小时终于写完了。