给定一个 DAG，定义
- 链：一条链内任意两点之间都存在一条路径
- 反链：任意两点都不存在路径
Dilworth 定理：最长反链 \(=\) 最小链覆盖。
最小链覆盖内一个点只能归属于一条链，但链不一定是连续的。
事实上这个还能转化为“选出若干条（一般定义下的）链，但一个点可以在多条链内”，本质相同。
求出 DAG 的传递闭包，则可转化为选出若干条链（指一般定义下的链），每个点只能在一条链内。
称这个问题为最小不可重链覆盖。
解决方法是，把每个点拆成 \(x_{in}, x_{out}\)，对于一条边 \((u, v)\) 连接 \((u_{out}, v_{in})\)。
最后求出最大匹配。
最小不可重链覆盖，显然选出链的条数为 \(n-\) 边数，而一个 \(x_{in}\) 或 \(x_{out}\) 只能对应一条边，于是显然边数为最大匹配。
于是答案为 \(n-\) 最大匹配。
在构造合法解之前，我们先来过一过二分图理论！！
- 最大独立集 $= n - $ 最小点覆盖
这个在一般图上也成立，求出任意最大独立集 / 最小点覆盖后取反即可。
- König 定理：最小点覆盖 \(=\) 最大匹配
证明：显然最小点覆盖 \(\ge\) 最大匹配。
以下构造可以构造出一组 \(=\) 最大匹配的最小点覆盖。
如何求最大匹配？一般做法是建图 \((S, u, 1), (u, v, 1), (v, T, 1)\) 再跑最大流。
根据 最大流=最小割，该图的最小割同样也是最大匹配。
最小割的构造：在残量网络上找出所有两个端点一个与 \(S\) 联通，一个不与 \(S\) 联通的边。
观察到最小割中隔断的边必然是 \((S, u, 1)\) 或 \((v, T, 1)\)，那取出所有这种点构成的点集即为最小点覆盖。
正确性显然，如果边 \((u, v)\) 中 \(u\) 和 \(v\) 都没被割掉，\(S-u-v-T\) 形成增广路。
来点 例题：CF1721F - Matching Reduction。
回到 Dilworth 定理的解构造上。
拿出二分图的最大独立集 \(I\)，把所有满足 \(x_{in}, x_{out} \in I\) 的 \(x\) 都取出来放到最长反链 \(A\) 里。
正确性：\(I\) 为独立集（注意到这依赖于你是对传递闭包建图的）。
最大性：
设 \(S\) 为最大匹配，则 \(I=2n-S\)，\(I-A\le n\) 故 \(A\ge I-n=n-S\)。
这样！我们构造出了一个大小至少是 \(n-m\)的反链！然后最小链覆盖的大小就是 \(n-m\)，反链的大小不会超过它，所以这个反链的大小就是 \(n-m\)，且是我们要求的最大反链。
标签：二分,匹配,最大,覆盖,定理,最小,Dilworth,反链,out From： https://www.cnblogs.com/fjy666/p/-/dilworth