【题解】丁香之路

ethan_zhou · 2022-03-04 21:03:55 · 题解

2024.10.14 更新： 修复格式

感觉这题的思路非常奇妙，就算会做了也完全不知道为啥要这么想。。。

题意

有一个 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^{\prime} 必定可以转化成贪心方法得到的解 E。

首先，我们把初始加的边（题目要求的 m 条边和 s\leftrightarrow i）称为黑边，其余的边叫白边。

引理

有且仅有一个 E 满足：

• E$ 中的白边边权都为 $1
• 在只考虑 E 中的边时，满足 2\mid\deg(i)

比较显然，证明略。

原结论证明

• 首先，把 E^{\prime} 所有白边 u\leftrightarrow v 都拆成若干 i\leftrightarrow i+1 的边，显然不劣（详见前文）。
• 然后，重复以下过程，直到 E^{\prime} 中不剩下任何一对白色重边：
  • 从 E^{\prime} 找到一对白色重边
  • 把这对边从 E^{\prime} 中删除
  • 把这条边加入 G 中（只加一次即可）

感性理解：

此时，如果只考虑 E^{\prime} 中的边，必然满足 2\mid\deg(i)。

由引理，此时 E^{\prime} 中的边，必定与恢复完度数奇偶性之后，E 中的边相同。