滑雪者 题解

Predawn_official · 2024-05-29 23:11:08 · 题解

编号：P8857

tag：网络流相关知识

难度：紫

这里提供一个转对偶图最长路的做法。

题目很显然是要求平面图最小链覆盖。由于这个图是 DAG 即一个有序偏序集，根据 Dilworth 定理可转化为平面图最长反链。

现在来证明一个定理：

Lemma 平面 DAG 的最小链覆盖 = 对偶图的最长路

注：这里的 最小链覆盖 指在有向无环图中用数量最少的简单路径覆盖图上的每一条边。

证明：

最小链覆盖 \ge 最长路并不难证。对偶图最长路就是原图的一个割，设划分的子集 S 和 T 的每一条边 (u,v),u\in S,v\in T 构成边集 E，有 \mid E\mid\le 最长路。很显然，由于这是一个 DAG，所以 E 中的每一条边必然最多属于一条链。

最小链覆盖 \le 最长路，我们将最小链覆盖转化为最长反链。将反链中的每一个点拆点 u^{\text{in}},u^{\text{out}}，并连边，那么最长反链可以看做是把对应点的所拆成的入点和出点所连的边断开。容易发现此时也构成一个割。若不是割那么存在一条通路，这条通路上选出跨过 S,T 的一条由入点和出点所连的边（必然能找到集合划分 S,T 使这样的边存在）断掉，而这组点对应原图上的点满足构成最长反链的条件。故构成割。而在平面图上的割可以转换为对偶图上的一条通路 L^\prime。显然有 \mid L^\prime\mid= 最长反链。可推得 \max\mid L\mid\ge 最小链覆盖。

故我们证明了 Lemma。

那么只要我们建出对偶图即可。

题目有一个很关键的条件，即给出的每个点的出边从西向东排列，那么我们便可以利用这个性质解题。

观察对偶图上的每一个点，除了源点和汇点，其他点均为形似这样的联通块：

其中，路径 a 在路径 b 西侧。

画出图形，我们可以得到结论，对于 a_i 指向的下一个点 x，有 x 是 a_i 指向的最靠东的边。相反地，对于 b_i 指向的下一个点 x，有 x 是 b_i 指向的最靠西的边。

那么我们便可以枚举 S,a_1,b_1，暴力找到每个对偶图上的点并建边。可以证明这样的时间复杂度是 \Theta(n+m) 的。每条边最多被作为左右两个对偶图上的点所遍历的边，所以遍历边是 \Theta(m) 的。至于点可以拆点类似遍历边的方式得出 \Theta(n) 的结论。

建出的对偶图求最长路跑一遍拓扑排序即可。