题解：CF21D Traveling Graph

· · 题解

CF21D Traveling Graph

一道图论好题，DP 部分因为比较简单倒在其次。

我们发现题目要求我们走出的路径类似一条欧拉回路，但是欧拉回路是不允许重复经过边的。怎么办？我们把问题转化成额外加入若干条边后走不重复边的欧拉回路，显然，我们要最小化加入的边的边权之和。

考虑一个图存在欧拉回路的充分必要条件？这太简单了，所有点度数均为偶数即可。考虑到加一条边意味着两端点度数 +1，我们可以想到一个朴素想法：把那些奇度点两两配对连边（显然奇度点有偶数个）。

但是我们只能加入原来就有的边，因为本质上“加边”还是重复经过已有的边。但是两条原图中不相邻的边真的就无法配对了吗？我们可以找到连接这两条边的最短路径，因为路径中间的点度数 +2，所以不会改变奇偶性。又注意到即使两个点原图上相邻，如果有更短的经过其它点的路径，仍应该选择最短路径。所以相不相邻根本就不重要，连接两个点的代价就是它们之间的最短路径。用 Floyd 算法容易预处理。

到这一步应该很容易 DP 出最优方案。把原图中的所有奇度点单独挑出来，令 dp_{S} 为当已经配对上的点集为 S 时，所花的最小代价。显然 dp_{\varnothing} = 0，转移方程为：

\mathrm{dp}[S] = \min_{j\in S\setminus\{i\}} \left\{ \mathrm{dp}\big[S\setminus\{i,j\}\big]+d(i,j) \right\}, \qquad i=\min S

其中 d(i,j) 为两点间最短路长度。

代码实现较为平凡，从略。