感觉这题的思路非常奇妙,就算会做了也完全不知道为啥要这么想。。。
题意
有一个 $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
本文为作者原创,转载请注明出处:本文链接
阅读量: