【学习笔记】最长反链和它全家（详细揭秘）

同志，扫盲了！

• 链：偏序关系中，链是形如 $a \leq b$ 的许多关系；$DAG$ 上，链是一个点集，其中任意两个点 $x$, $y$ 都能从 $x$ 到 $y$ 或从 $y$ 到 $x$。

• 反链：反链也是点集，不过其中任意两个点都不能走到彼此。

最长反链 = 最小链覆盖（Dilworth 定理：最长反链 = 最小链精确（即不可重）覆盖，通过传递闭包可以转为最小链可重覆盖，然而实现时都用网络流）
最长链 = 最小反链覆盖

• 最大匹配：$DAG$ 的最大匹配概念同二分图的。

• 最小链覆盖：也叫最小路径覆盖，作用如其名，分为可重和不可重。

最小链覆盖 = 顶点数 - 最大匹配（刚开始没有匹配，显然成立；接下来每匹配一对点，匹配数 +1，路径数 -1。匹配数 = 每条路径点数边数和。）

• 最小不可重链覆盖：拆点，用匈牙利算法或者网络流求解，连 $(x_{out}, y_{in})$

• 最小可重链覆盖：先传递闭包，再在形成的偏序集上做最小不可重链覆盖，跳过的点被当作重复经过，然而实现时一般用网络流建 $(x’, x, \infty)$ 这样的反边表示某些点被当作中间点做了传递闭包。

• 最大独立集：选出最多的点，其中两两无边相连。

二分图 最大团 = 补图最大独立集

• 最小点覆盖：选择最少的点覆盖所有边。

  • 二分图的最小点覆盖可以这么求：先跑一遍最大匹配，令左边点只能走非匹配边，右边点只能走匹配边，最小点覆盖就是左侧未访问点加上右侧已访问点。

• 最小边覆盖：选择最少的边覆盖所有点。

二分图 最大匹配 = 最小点覆盖
    每条边一定连着一个匹配点，否则连两个未匹配点匹配数应该 +1。
二分图 最大独立集 = 顶点数 - 最小点覆盖
    把最小点覆盖剔除，剩下的点就没有边相连了。
二分图 最小边覆盖 = 顶点数 - 最大匹配
    显然。同时也告诉我们最小边覆盖就是在最大匹配的基础上加边，变成完美匹配。
二分图 最小割 = 最小点权覆盖集 = 点权和 - 最大点权独立集

感觉类似题目（不 sb 的那种）都是用👆上面这套理论搞来搞去，比如 $CTSC2008-祭祀$：难点在构造方案。

第二问好想，每个点删除后做一遍最长反链看是否只减小了 $1$。

第一问，先说结论：选出新图所有 $x_{out}$ 和 $x_{in}$ 都在最大独立集里的点，就是原图最长反链。

证明：
有最大独立集合 $I$ = 顶点数 $2n$ - 最大匹配 $m$，设最长反链集合为 $A$，$I - A$ 为「$x_{out}$ 或 $x_{in}$ 在最大独立集里」的点集，$|I| - |A| \leq n$, $|A| \geq |I| - n = n - m$, 而 $|A| \leq n - m$，所以 $|A| = n - m =$ 原图最长反链。

所以匈牙利或者 $dinic$ 找最大匹配，再 dfs 找最小点覆盖，最大独立集 = 最小点覆盖补集。注意这题可重。

彩蛋：$dinic$ 在二分图上单次增广是 $O(n\sqrt{n})$ 的哦

upd: $96$ 分我太疑惑了？