本文慢慢整理部分模型。
DAG 最小路径覆盖
经典的题目，经典的思想。
网络流常见的将图上的点拆为入点和出点，那么路径由若干 出 - 入 - 出 - 入 的循环构成。
于是在拆好的图上流一流即可。
[CTSC2008] 祭祀 典中祭
黑白染色
利用黑白染色将整个图变成一个二分图是网络流常见的套路，尤其是在有 棋盘 状物出现的时候。
P3355 骑士共存问题 黑白染色，稍微搞搞就完事。
最小割
最大流等于最小割，这是一个对偶问题。
最小割的构造
从源点开始在残量网络上沿着有剩余流量的边走，这会走出一个连通块。
走到的点集为 \(S\)，剩下的为 \(T\)，那么最小割我们只需要选择 \(S, T\) 相交的那些边即可。
由于搜索的过程沿着有剩余流量的边走，所以一定满流。
最小割的可能与一定
可行边满足：
- 满流
- \(x \to y\) 没有可用流量
必要边满足：
- 满流
- \(S\) 可以通过有剩余流量的边走到 \(x\)，而 \(y\) 可以走到 \(T\)
最小割与二选一问题
P4313 文理分科 典中典。
二选一如果是可行性那么首先联想 2-SAT，如果是收益联想最小割。
考虑最小割使得 \(S, T\) 不连通，那么对于某一个元素 \(x\)，设选 \(A\) 的收益为 \(A_x\)，选 \(B\) 则为 \(B_x\)，那么连出类似于 \(S \stackrel{A_x}{\to} x \stackrel{B_x}{\to} T\) 的图，看是最大化还是最小化选择最小割还是其补集。
P2774 方格取数问题 差不多，不能相邻，也可以转化为 x选x 问题。
P1646 [国家集训队] happiness 令人 happy 的题。
# [Ceoi2008]order 多了一小点东西的最小割。
最小割树
如此构造，初始化当前点集 \(S\) 为所有点：
- 随机两个点 \(x, y\)，求出其最小割 \(cut\)，在树上连边 \(x \stackrel{cut}- y\)。
- 利用最小割将点集划分为小的两个点集，递归上述操作。
如此我们可以构造出一个树，使得两点之间的 \(cut\) 即是树上路径最小值。
考虑如果 \(x \to y\) 的割是 \(cut\)，那么两边点的 \(cut\) 一定不大于 \(x \to y\) 的 \(cut\)，否则 \(x \to y\) 就没法割掉。
然后就随便做了。
P4897 【模板】最小割树（Gomory-Hu Tree）