感觉这题的思路非常奇妙，就算会做了也完全不知道为啥要这么想。。。
题意
有一个 $n$ 个点的无向完全图，边 $i\leftrightarrow j$ 的边权为 $|i-j|$，强制经过指定的 $m$ 条边，求起点为 $s$，终点为 $i\in[1,n]$ 的最短路径。$n\le 2500,m\le \frac{n(n-1)}2$。
思路
考虑在一个可重无向边集 $E$，如果：
- $\text{必须经过的}\ m\ \text{条边}\subseteq E$
- 存在一条 $s\leftrightsquigarrow i$ 的欧拉路径
那么就有符合题目要求的一条路径存在。答案即为符合条件的 $\sum_{i\in E} w_i$ 的最小值。
一开始，我们就先把题目要求的 $m$ 条边加到 $E$ 里面，这样 $E$ 就天然满足第一个条件。
欧拉路径不太方便搞，我们一开始就往 $E$ 中加一个 $s\leftrightarrow i$，这样第二个条件就变成了“存在一条欧拉回路”。
存在欧拉回路的条件：
- $2\mid\deg(i),\forall i\in[1,n]$
- 图联通
下面说如何向 $E$ 中添加若干条边，使得 $E$ 满足上面两个条件，并且让这些边的边权和最小（先说做法，再写证明）
恢复度数奇偶性
把所有 $2\nmid\deg(i)$ 的 $i$ 拿出来，按编号排序。然后把相邻的奇度点两两配对（第 $2k$ 小的和第 $2k-1$ 小的配对）连边（图中红色为奇度点，蓝色为加的边）：
注：做法中所说的连边并不是说直接连 $u\leftrightarrow v$。而是连（这样连边显然更优）：
\[\begin{aligned} u&\leftrightarrow u+1\cr u+1&\leftrightarrow u+2\cr u+2&\leftrightarrow u+3\cr \vdots \cr v-1&\leftrightarrow v \end{aligned}\]
联通性
建完前文所述的边之后，图缩成若干连通块。只要再加一些边，把这些联通块联通起来即可，可以看出，这是一个类似最小生成树的东西：
把所有 $\deg(i)\neq0$ 的 $i$ 拿出来按编号排序（度数为 0 的点不需要被联通），把相邻的两个点之间的的边拿去做 Kruskal 即可。所有在最小生成树上的边都会被经过两次。
复杂度 $O(n^2 \log n+m)$。
证明
下证任何一组最优解 $E’$ 必定可以转化成贪心方法得到的解 $E$。
首先，我们把初始加的边（题目要求的 $m$ 条边和 $s\leftrightarrow i$）称为黑边，其余的边叫白边。
引理
有且仅有一个 $E$ 满足：
- $E$ 包含指定的 $m+1$ 条黑边
- $E$ 中的白边边权都为 $1$
- $E$ 中没有白色重边
- 在只考虑 $E$ 中的边时，满足 $2\mid\deg(i)$
比较显然，证明略。
原结论证明
- 首先，把 $E’$ 所有白边 $u\leftrightarrow v$ 都拆成若干 $i\leftrightarrow i+1$ 的边，显然不劣（详见前文）。
- 然后，重复以下过程，直到 $E’$ 中不剩下任何一对白色重边：
- 从 $E’$ 找到一对白色重边
- 把这对边从 $E’$ 中删除
- 把这条边加入 $G$ 中（只加一次即可）
感性理解：
- $E$ 中的白边对应恢复度数奇偶性过程中加的边
- $G$ 中的边对应做最小生成树过程中加的边
此时，如果只考虑 $E’$ 中的边，必然满足 $2\mid\deg(i)$。
由引理，此时 $E’$ 中的边，必定与恢复完度数奇偶性之后，$E$ 中的边相同。
$G$ 中的边的目的就是把 $E’$ 形成的连通块缩到一起，与贪心做法中的 MST 是等价的。
证毕。
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: