网络流模型 · 最小路径覆盖 & 拓展
定义
在一个 DAG（有向无环图中），选择其中的一些简单路径，若图中每个点都恰好在其中一条路径上，则称这些路径是一个路径覆盖。
所有路径覆盖中，路径条数最小的路径覆盖叫做最小路径覆盖。
任务是找出 DAG 上的最小路径覆盖，且输出方案。
建模
考虑二分图最大匹配。
我们对原图中每个点 $u$ 拆成两个点，记为左部点 $L(u)$ 和右部点 $R(u)$。
对于原图中每条边 $(u,v)$，连接 $L(u)$ 到 $R(v)$。
则答案为原图中点数减去最大匹配数。
正确性
假设开始时图上的每个点都自成一条路径，我们要做的是尽可能多地把路径合并。
考虑一下路径合并的隐藏条件：
首先，路径合并是可以传递的，简单来说，如果 $x$ 能跟 $y$ 合并，$y$ 能跟 $z$ 合并，那么 ${x,y,z}$ 可以合并成一条路径。所以我们可以只考虑点与点之间的合并关系，再利用传递性求方案。
其次，每条路径只能向一个路径合并，也只能被一条路径合并。
这下就好办了。在我们构造的二分图中，如果一条边 $(L(u),R(v))$ 被选中了，那么说明在原图中点 $u$ 要向点 $v$ 合并，同时其它在二分图中与其它 $L(u)$ 相连的边都不能被选中，对应着在原图中一个点仅能选择另外一个点进行合并。
此时的最大匹配就是可以合并的数量，用总的点数减去它就是答案。
至于方案数，可以根据上面所说的，用并查集简单维护即可。
二分图的最大匹配我们可以选择用最大流来求。跑完最大流后，如果一条连接 $L(u)$ 和 $R(v)$ 的边容量为 $0$，则说明这条边在二分图中被选中了。
拓展 1 · 最小链覆盖
所谓最小链覆盖，无非是把路径改为了链。对应的，DAG 上的每一个点可以被重复覆盖多次。
此时我们对 DAG 用 Floyd 进行传递闭包，得出每个点相互可不可达，再根据这个跑最小路径覆盖即可。
拓展 2 · DAG 最大独立集
顾名思义，我们要在 DAG 中选取一些点，使得任意两个点都不能从其中一个点到另外一个。
此时我们引入偏序集。
偏序集
偏序集和偏序关系
我当然不会上来就放形式化的东西，否则你们还有什么来看的必要呢？
所谓偏序集，指的是一个集合和一个关系的共同体。
那么何为关系？举个最简单的例子，“$\leq$”（小于等于号）是一个关系。
现在我们给偏序集做一个定义，百度说：
若在集合 $A$ 上给定一个偏序关系 $\leq$ ，则称集合 $A$ 按偏序关系 $\leq$ 构成一个偏序集合，集合 $A$ 和偏序 $\leq$ 一起称为偏序集，记作 $(A,\leq)$。
不懂。什么是偏序关系？
设 $R$ 是集合 $A$ 上的一个关系，如果 $R$ 是自反的、反对称的和可传递的，则称 $R$ 是集合 $A$ 的偏序关系，简称偏序，记作“$\leq$”。
现在对偏序关系中的一些名词做一些解释：
自反：$\forall a\in A,a\leq a$
反对称：$\forall a,b\in A, $ 若 $a\leq b$ 且 $ b\leq a,$ 则 $a=b$
传递性：$\forall a,b,c\in A, $若$ a\leq b $且$ b\leq c, $则$ a\leq c$
不妨把这个小于等于号真的当做一个小于等于号来看待，则 $\leq$ 是 $\mathbb{R}$ 的偏序关系。
所以我们可以说 $(\mathbb{R},\leq)$ 是一个偏序集。
元素之间的可比关系
设 $(P,\leq)$ 是一个偏序集。
$a,b\in P$，若 $a\leq b$ 或 $b\leq a$，则我们称 $a$ 与 $b$ 是可比的。无需解释。
否则我们说 $a$ 与 $b$ 不可比，记作 $a\mid\mid b$。
延伸
设 $(P,\leq)$ 是一个偏序集，$\geq$ 是一个关系。
若对于 $\forall x,y\in P$，有 $x\leq y \Leftrightarrow y\geq x$，则我们称 $\geq$ 是 $\leq$ 的逆关系，记作 $\leq^{-1}$。$\leq^{-1}$ 是 $\leq$ 的逆。无需解释，符号已经说的很明白了。
那么，若 $(A,\leq)$ 是一个偏序集，$(A,\leq^{-1})$ 也是一个偏序集。这是显然的。$(A,\leq^{-1})$ 称作 $(A,\leq)$ 的对偶，简记作 $A^{-1}$。
偏序集的哈塞图
所谓哈塞图，不如将其理解为一个 DAG。
设 $(P,\leq)$ 是一个偏序集，我们对于 $\forall a,b(a\neq b)\in P,$ 若 $a\leq b$ 则从 $b$ 到 $a$ 连一条边，最后显然会形成一个 DAG。（根据传递性可得到图中没有环）
链、反链、Dilworth 定理
偏序集 $(P,\leq)$ 上的一个链是一个元素集合 $S \subset P$，其中 $\forall a,b\in S,a$ 与 $b$ 可比。
反链就是反着来，也是一个元素集合 $S\subset P$ 其中 $\forall a,b\in S,a\mid\mid b$。
需要注意的是，链在 DAG 中并不是一条路径，而是一条路径上可以不连续的几个点，但是在后续我们为了方便，把链看成 DAG 上的一条路径，反链就是一些 DAG 上互相不可达的点。
接下来我们引入偏序集的链划分。
所谓链划分，就是一些链的集合，使得偏序集的每一个元素都在其中至少一条链上。
最小链划分就是用最少的链来把整个偏序集覆盖，对应到 DAG 上就是最小链覆盖。
Dilworth 定理指出，偏序集中的最长反链长度等于最小链划分个数。
证明略，感兴趣的可以尝试对偏序集的大小进行归纳证明。
模型
看到这里是不是恍然大悟了，我们在原 DAG 上求最小链覆盖，得到的答案就是最大独立集大小。