题解：P10938 Vani和Cl2捉迷藏

_jimmywang_ · 2025-01-16 00:41:12 · 题解

题意：求 DAG 的最长反链长度。

反链的概念来源于序理论，此处稍作简化处理。

因为偏序集可以视作一个 DAG，偏序关系即为有向边，此处为方便，将序理论中的概念迁移至 DAG 上。

定义 DAG 上两点 u,v 是可比的，当且仅当存在一条 u\to v 或 v\to u 的有向路径，反之 u,v 是不可比的。定义链为一个点集 S，使得任意两点 u,v\in S，u,v 都是可比的；定义反链为一个点集 T，使得任意两点 u,v\in T，u,v 都是不可比的。

简单地说，链就是一条 DAG 的路径的子集，反链就是一个点集，其中的点两两没有有向路径连接。

做法1：最大权闭合子图

因为选了一个点，其所有的后继节点（可传递）均不能选，因此我们建立以下模型：

对原图每个点拆点 (in_u,out_u)，原图边 (u,v) 改为 (out_u,in_v)，所有 in_u 点权为 -1，所有 out_u 点权为 1。此图最大权闭合子图即为最长反链。

这个图比较好理解，因为一个最大的闭合子图一定是由若干个 out_u 作为起点发出的（否则权值和非正），这几个 u 构成了一个反链。

做法2：Dilworth 定理

Dilworth 定理的表述：最长反链等于最小链覆盖。注意区分此处的链与路径。链是点集，不一定要求是一条路径。

证明采用归纳形式，详见 oi-wiki。

最小链覆盖的做法并不困难：先对原图做一遍传递闭包，此时所有的链都转化为了传递闭包后的图上的路径，此时再做最小路径覆盖的答案就是原图上最小链覆盖的答案。