[贪心] [欧拉回路] P6628 丁香之路

_Cheems · 2023-11-05 14:15:57 · 个人记录

题目链接

神仙贪心题，初看根本没有头绪QwQ

首先把 m 条路建成一个图，我们对该图进行讨论。

最简单情况：图连通，且有欧拉路 s\to t，答案即为原边权之和。

如果图连通、但无欧拉路怎么办？有两个选择：建新边使欧拉路存在和同一条边重复走。

注意到 w_{u,v} = |u-v|，因此任两点的最短路径一定是直接走 u\to v 这条边，所以建新边一定不劣于重复走多次。

由这一点可知，题面的“至少走一次”等价于“恰好走一次”。那么就是个欧拉路径问题。

不过直接求欧拉路径不好做，转换下试试：“s\to t 的欧拉路径”等价于“连接虚边 s,t，以 s 为起点走欧拉回路”。

（虚边的意思就是这条边存在但是边权为 0）

然后不需考虑连通性，可以把度为奇数的点抽出来并排序，两两连边。由绝对值性质知这样做一定最优。

（无向图中一定有偶数个奇点）

那么图不连通的情况呢？直接建边跑最小生成树即可，为了不影响奇偶需乘二。

不过这样做边数是 n^2 级别的。实际上只需将两相邻点之间的边加入候选边即可，边数降为 n 级别。当然这些点必须与 m 条边有关。

为什么这样连边一定有解？还是因为绝对值的性质！首先易知任意两连通块一定有路径可达（考虑绝对值的几何意义）。

又因为 a<b<c 时 |a-b|+|b-c|=|a-c|，所以 a\to b,b\to c 不劣于直接 a\to c，这便保证了得到的是最优解。

以为这就结束了？上述贪心策略还不够贪，还需将“两奇点 s,t 连边” 改为“连接两奇点之间的所有点，即 s\to s+1,s+1\to s+2...t-1\to t”，这样便在代价不变的情况下连接了更多边。

提交记录

首先把所有有关点放到数轴上，s\to t 的边权就是 s,t 两点的距离。

有没有可能，不连接两两相邻的奇点，而是把连通性也考虑进去更优呢？

（也就是连接的边有相交）

我认为贪心策略的正确性，与“连接两奇点之间的所有点”这一做法有关。因为这样做后，容易发现 s\to t 的所有点都被加进同一连通块，进一步可知最终连接的所有边都互不相交。

考虑四个奇点 a<b<c<d，假如存在一最优解 a\to c,b \to d，那么我们的贪心策略一定会包含 a\to b,b\to c, c\to d 这一情况，显然花费更少，还连接了更多点。

换句话说，一定存在一种“线段互不相交”的花费不多于“线段相交”的花费，并且连接的连通块更多。上述贪心策略的正确性得以保证。