P10938 最长反链大小

· · 题解

如果读者对序理论有所了解，则容易发现这是求解最长反链大小的模板题。通常而言，求最长反链需要借助 Dilworth 定理转化为最小链分解，这也是本题解给出的方式。@_jimmywang_ 则指出了一个最大权闭合子图的做法。

在下面的内容中，我将先介绍序理论的基本概念，并给出 Dilworth 定理的证明。对此已有了解的读者，可跳过此部分。

定义 1. \quad 设 P 为集合，资料 (P,\leq) 被称作偏序集；其中 \leq:P\times P\to\{0,1\} 是 P 上的二元关系 (偏序)，满足

  1. 反身性：\forall x\in P,x\leq x；
  2. 传递性：(x\leq y)\land(y\leq z)\Longrightarrow x\leq z；
  3. 反称性：(x\leq y)\land(y\leq x)\Longrightarrow x=y。

特别地，用 x<y 表示 x\leq y 且 x\neq y。\blacksquare

容易发现，在 P=\{x_i\}_1^{|P|} 有限时，\leq 的取值可表为一个 |P| 阶方阵 \Gamma_P=(p_{ij})_{1\leq i,j\leq|P|}，其中 p_{ij}=1\iff x_i\leq x_j。以 P 为邻接矩阵可得一个 DAG。换言之，对于有限的偏序集，若 x\leq y 则由 x 向 y 连边，则总可以得到一个 DAG。

定义 2. \quad 若偏序集 P 的任意一对元素 (x,y)\in P^2 皆可比（即，或者 x\leq y，或者 y\leq x），则称 P 为全序集或链。若 集合 E\subset P 满足 \forall (x,y)\in E^2，x\leq y 与 y\leq x 皆不满足，即 x,y 不可比，则称 E 是一条反链。称偏序集 P 的最长反链的大小为 P 的宽度。\blacksquare

定义 3. \quad 设 E\subset P，P 为偏序集。

同理可定义极小元、下界与下确界。\blacksquare

下面将给出的 Dilworth 定理是本题解做法的关键。

定理 4. (Dilworth) \quad 设偏序集 (P,\leq) 的宽度为 m，则存在划分 X=\bigcup_1^mC_i，其中每个 C_i 皆为链。

证明 \quad 首先 P 显然不能被划分为更少的链。下面对 |P| 归纳。当 |P|=1 时，结论显然成立。假设结论对 <|P| 成立，考察 |P| 的情形。

设 C_1 为 P 的一个极大链，考察 P\backslash C_1。若 P\backslash C_1 宽度为 m-1 则结论显然成立。

若 P\backslash C_1 的宽度为 m，则设 \{a_i\}_1^m 为它的一条反链，定义 S^-:=\{x\in P:\exists i\text{ s.t. }x\leq a_i\},S^+:=\{x\in P:\exists i\text{ s.t. }x\geq a_i\}。因 (P,\leq) 的宽度为 m，可知 S^-\cap S^+=\{a_1,\cdots,a_m\} 且 P=S^-\cup S^+。由于 C_1 为极大链，C_1 的最大元不能在 S^- 中。由归纳假设知，S^- 与 S^+ 皆可划分为 m 个链 S_i^-\,(i=1,\cdots,m) 与 S_j^+\,(j=1,\cdots,m)。易知 a_i 为 S_i^- 的最大元与 S_i^+ 的最小元。将 S_i^- 与 S_i^+ 由 a_i 合并，即将 P 分为了 m 个链。\square

下面回到本题来。容易发现，DAG 上可达性自然地构成了一个偏序，即，若将 DAG 的传递闭包中的有向边看作偏序关系，则它构成了一个偏序集。显然，本题中的“藏身点”需要是一条反链。因此本题正是让我们计算该偏序集的宽度，或者说其最长反链的大小。

运用 Dilworth 定理，则问题转化为求链分解的最小数目。容易发现这就是传递闭包图上的最小路径覆盖问题，运用 P2764 最小路径覆盖问题 的做法即可。

具体地，将原图每个点 x 拆为 x_1,x_2 二点，若满足 x<y 则连边 (x_1,y_2)，形成一张二分图。该图的任意一个匹配中的一条匹配边 (u_1,v_2) 代表传递闭包图上 u,v 两点合并为一条路径。容易看出，匹配中一个点至多连一条匹配边的性质满足了一个点只能被一条路径覆盖的要求，故一个匹配对应一个路径覆盖，反之亦然。注意到一条匹配边会使路径数量减一，从而设最大匹配为 x，则 n-x 即为最小路径覆盖，也就是最长反链的大小。

欲求一条具体的最长反链，可看 [CTSC2008] 祭祀（这题是最长反链模板的完全体）。@_jimmywang_ 则给出了一个不依赖 Dilworth 定理的做法。