Dilworth 定理与二分图部分理论
给定一个 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\)，且是我们要求的最大反链。
模板：P4298 - [CTSC2008] 祭祀
模板微调：CF590E - Birthday
让我们来点 高性能 优化！
最大权独立子图为如下问题：
- 给定一张有向图，每个点都有权值 \(v_i\)
- 定义一个独立子图为 \(S\subseteq \{1,2,\cdots, n\}\)，满足对于所有 \((u,v)\in \mathbb{E}\)，\(u\in S\Rightarrow v\in S\)
- 需要找到内部权值和最大的独立子图。
解法可以参见链接。
考虑将原图的点拆成两个点，\(u_{+}\) 和 \(u_{-}\)，点权分别为 \(1\) 和 \(-1\)，从 \(u_{-}\) 向 \(u_{+}\) 连边。
对于原图中的每条边 \((u, v)\)，连边 \(u_{+}\to v_{-}\)，最后求整个图的最大权独立子图即为最长反链。
考虑一个点 \(u\)，\(u\) 对最大权独立子图的贡献要么是 \(1\)（仅有 \(u_{+}\) 在里面），要么是 \(0\)（都不在里面或者都在里面）。最长反链即为所有贡献是 \(1\) 的节点。
显然，假如 \(u\) 的贡献是 \(1\)，所有 \(u\) 能到达的点的贡献均为 \(0\)，因此满足“不能互相到达”的条件。
由于无需求出传递闭包，时间复杂度为 \(\mathcal{O}(m\sqrt{n})\)。
构造“最长反链”的方法是平凡的。