题解 P4298 【[CTSC2008]祭祀】

题目要求的实际上是一个偏序关系的**最长反链**，通过 Dilworth 定理可以发现就是 DAG 的**最小可重复路径点覆盖**。 最小可重复路径点覆盖又可以通过 $\mathcal O(n^3)$ 的传递闭包转化为**最小路径点覆盖**。 又 DAG 的最小路径点覆盖包含的路径条数 $= n -$ 其**拆点二分图**的最大匹配数。 使用**匈牙利算法**即可在 $\mathcal O(n^3)$ 的时间求出答案。 接下来的问题是如何构造方案。 我们先求出传递闭包后的图的最小路径点覆盖包含的路径集合 $path$： 1. 设在拆点二分图中左部点 $x$ 对应的右部点为 $x^{\prime}$，若 $x,y$ 匹配则有 $f_x = y, f_y = x$。 2. 依次考虑左部的每一个非匹配点 $x_0$。 3. 从 $x_0$ 出发，每次从 $x$ 走到 $f_{x^{\prime}}$，直至到达一个左部点 $y_0$，满足 $y_0^{\prime}$ 是非匹配点。 4. 那么经过的所有点构成一条以 $y_0$ 为起点 $x_0$ 为终点的路径。 接下来我们要从 $path$ 的每条路径上选出一个点构成原图的最长反链： 1. 将所有的终点 $x_0$ 放到一起构成一个集合 $E$。 2. 求出从 $E$ 中的所有节点出发，走一条边，到达的所有节点 $next(E)$。 3. 根据传递闭包的性质，若 $E$ 与 $next(E)$ 没有交，那么 $E$ 即为所求。 4. 否则考虑 $E \cap next(E)$ 的所有节点 $e$，沿着 $e$ 所在的路径反着走，直到一个节点 $e^{\prime} \notin next(E)$，在 $E$ 中将 $e$ 替换为 $e^{\prime}$。 5. 回到第 $3$ 步。