自动搬运

查看原文

来自洛谷，原作者为

	ethan_zhou 博客：blog-e.top

搬运于2025-08-24 22:22:34，当前版本为作者最后更新于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$ 包含指定的 $m+1$ 条黑边
• $E$ 中的白边边权都为 $1$
• $E$ 中没有白色重边
• 在只考虑 $E$ 中的边时，满足 $2\mid\deg(i)$

比较显然，证明略。

原结论证明

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

感性理解：

• $E$ 中的白边对应恢复度数奇偶性过程中加的边
• $G$ 中的边对应做最小生成树过程中加的边

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

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

$G$ 中的边的目的就是把 $E^{\prime}$ 形成的连通块缩到一起，与贪心做法中的 MST 是等价的。

证毕。