次短路 & 次小生成树 学习笔记

# 次小生成树 ### 1. 最小生成树 #### 1.1 最小生成树问题的求解 设有一无向连通图 $G=(V,E)$，$E$ 中边带权。其最小生成树（*Minimum Spanning Tree*）就是 $G$ 的所有**生成树**中边权和最小的一棵。 以下记 $|V|=n$，$|E|=m$。 MST 问题的求解分为**破圈法**和**避圈法**两类，以下三种均属于破圈法。 - *Prim*。最坏 $\Theta(n^2)$，主要适用于**完全图**或**稠密图**。 - *Kruskal* 。 最坏 $\Theta(m\log m)$，是最常见的求法。 - *Boruvka* 。最坏 $\Theta(m\log n)$ ，是效率最高的求法，不过要求**图中边权互不相同**。 #### 1.2 最小异或生成树 实际上，*Boruvka* 算法的思想一般用于求解**最小异或生成树**。 *Boruvka* 算法求最小生成树的主过程： 1. 建立 MST 的边集 $E^\prime$，初始时 $E^\prime=\varnothing$。 2. 根据 $E^\prime$ 求出每个点所在的连通块 $a_i$，并将每个连通块的“最小边” $b_i$ 设为 $\infty$。 3. 遍历每条边 $(u,v,w)$，若 $u$ 和 $v$ 不在同一个连通块，执行 $b_{a_u}\gets \min\{b_{a_u},w\}$。 4. 若所有连通块中 $b_i=\infty$，退出过程。否则将所有不为 $\infty$ 的 $b_i$所在的边加入 $E^\prime$，返回第 2 步。 由于每次迭代连通块数量至少减半，因此至多迭代 $\Theta(\log n)$ 次，复杂度 $\Theta(m\log n)$。 > **例题**：[CF888G](https://codeforces.com/problemset/problem/888/G)（[洛谷入口](https://www.luogu.com.cn/problem/CF888G)） 显然在第 3 步时，我们不能遍历完全图中的每条边。 异或问题主要采用 *01 trie* 或 *线形基* 解决，此题显然不能用线形基，则先建一棵 *01 trie*，将所有的 $a_i$ 插入。 首先，若 $\exists i\ne j,a_i=a_j$，考虑给 $(i,j)$ 连边，边权必为 $0$。连边后， $i$ 与 $j$ 相当于同一个点，因此我们忽略这种情况。 不难发现，既有左儿子又有右儿子的节点个数为 $n-1$ 个，这 $n-1$ 个点就是**我们需要连的边在 *trie* 上所对应的点**。 *Boruvka* 算法的主过程就是**在每个已有的连通块中找出一条最短的外连边**，并连上。 在此问题中这样能尽可能减少差值，使连通块的外连边只连向它的兄弟。 现在，问题转化为：在这 $n-1$ 个点的子树中分别找出两条路径，使它们的异或和最小。 **直接找这两条路径不！是！N！方！的！！！复杂度 $O(n\log n)$！** 我在这儿卡了一年，后来发现树高至多为 $30$...... 那么贪心地把这两条路径找出即可。 [Code](https://www.luogu.com.cn/record/53224333) >复杂度证明如下： > >显然这 $n-1$ 个点互不相同，它们中最深的点高度最小为 $\Theta(\log n)$，此时个数为 $\Theta(n)$。 > >这 $n-1$ 个点中的叶子结点的子树总大小最大为 $30n-n=\Theta(n)$，其中每棵均摊被遍历到 $\Theta(\log n)$ 次。 > >因此复杂度最大为 $\Theta(n\log n)$。 ### 2. 次小生成树 次小生成树分为**严格次小生成树**和**非严格次小生成树**。 #### 2.1 非严格次小生成树 求非严格次小生成树的主要思路是**在最小生成树中找到一条边，用非树边换掉**。 1. 求出最小生成树 $T$，设边权之和为 $S$。 2. 树上倍增，预处理每个点到其 $2^i$ 级祖先的边权中最大值。 3. 从小到大遍历不在树中的所有边 $(u,v,w)$，在树上求出 $u$ 到 $v$ 路径上最大的边权 $z$，用 $S-z+w$ 更新答案。 时间复杂度 $\Theta(m\log m)$。 可以说明，若非严格次小生成树的边权和等于最小生成树的边权和，则最小生成树不唯一。 #### 2.2 严格次小生成树 实际上二者的求法思路相同，不过严格的更难求。 1. 求出最小生成树 $T$，设边权之和为 $S$。 2. 树上倍增，预处理 $j$ 号点到其 $2^i$ 级祖先 $fa_{i,j}$ 的边权中最大值 $f_{i,j}$ 和**严格次大值** $g_{i,j}$（没有则为 $-1$） 具体地，有： $$ f_{i,j}=\max\{f_{i-1,j},f_{i-1,fa_{i-1,j}}\} $$ $$ g_{i,j}=\begin{cases} \max\{f_{i-1,j},g_{i-1,fa_{i-1,j}}\}&f_{i-1,j}<f_{i-1,fa_{i-1,j}}\\ \max\{g_{i-1,j},f_{i-1,fa_{i-1,j}}\}&f_{i-1,j}>f_{i-1,fa_{i-1,j}}\\ \max\{g_{i-1,j},g_{i-1,fa_{i-1,j}}\}&f_{i-1,j}=f_{i-1,fa_{i-1,j}}\\ \end{cases} $$ 3. 从小到大遍历不在树中的所有边 $(u,v,w)$，在树上求出 $u$ 到 $v$ 路径上最大的边权 $z$。 若 $z=w$，则取 $z$ 为次大边权（依照上式方法进行合并）。再用 $S-z+w$ 更新答案。 时间复杂度 $\Theta(m\log m)$。 > **例题**：[P4180 [BJWC2010]严格次小生成树](https://www.luogu.com.cn/problem/P4180) [Code](https://www.luogu.com.cn/record/53237957) ``` #1 Input: 7 15 6 3 35 1 6 44 3 2 22 2 7 57 5 1 57 5 6 65 5 3 44 7 4 57 7 2 44 7 1 44 4 5 44 4 5 44 2 3 65 1 7 44 1 2 44 Output： 242 ``` # 次短路 ### 1. 最短路 以下均指**单源最短路**（*Single Source Shortest Path*）问题。 解法一般有： - *Bellman-Ford* 和 *SPFA*。最坏 $\Theta(nm)$，尽量不使用。 - *Dijkstra*。最坏 $\Theta(n^2)$，一般适用于完全图。 - 堆优化 *Dijkstra*，最坏 $\Theta(m\log n)$，是最常用的求法。 当然也可把堆换为斐波那契堆以获得更优复杂度。 ### 2. 次短路 同样，次短路也分为**严格次短路**和**非严格次短路**。 有两种常用做法： #### 2.1 *k* 短路 注意到非严格次短路其实就是 $k=2$ 时的情况，因此可以直接套板子。 求严格次短路也很简单，不再赘述。 #### 2.2 类似最短路的做法 其实十分简单，直接修改最短路的松弛条件即可。 ```c++ if(dis[y]>dis[x]+edge[i]) { dis2[y]=min(dis[y],dis2[x]+edge[i]); dis[y]=dis[x]+edge[i]; q.push(make_pair(dis[y],y)); } else if(dis[y]<dis[x]+edge[i] && dis2[y]>dis[x]+edge[i]) { dis2[y]=dis[x]+edge[i]; q.push(make_pair(dis2[y],y)); } else if(dis2[y]>dis2[x]+edge[i]) { dis2[y]=dis2[x]+edge[i]; q.push(make_pair(dis2[y],y)); } ``` 由于每个点最多被松弛 $2$ 遍，所以复杂度依然是 $\Theta(m\log n)$。 **例题**：[P2865 [USACO06NOV]Roadblocks G](https://www.luogu.com.cn/problem/P2865) [Code](https://www.luogu.com.cn/record/53279746) 完结撒花~~