（网络流这玩意sb毁我青春）（从 url 可以看出来）
由于我这方面太菜了所以稍微复习一下下（但复习完还是很菜）
不要妄想从这里找到任何有用的信息，因为我是瞎 jb写的
二分图
最大匹配
KM 辣鸡，Dinic txdy。\mathcal{O}(m\sqrt{n})。
P.S. 不加当前弧优化的 Dinic 的复杂度是错的，是错的，是错的！！
Dinic 解决多重匹配也很方便，复杂度不变。
P.S. 对于一般图来说，如果存在图一个割满足所有边流量都为 1，那么跑 Dinic 的复杂度也是 \mathcal{O}(m\sqrt{n})。
最大独立集
最大独立集=总点数-最大匹配
P.S.
一般图最大独立集=补图的最大团
关于输出方案：
残量网络上与 S 连通的左部的点以及与 S 不连通的右部的点。
例题：
最小点覆盖
最小点覆盖=最大匹配
用最小点覆盖求解问题时，限制都是形如：两个东西最多只能选其中一个。
例题：
可行边与必须边
先跑出来个最大匹配。
$(u,v)$ 是必须边当且仅当：$(u,v)$ 是当前的匹配边 **且** $u$ 和 $v$ 在残量网络上**不是**同一个 SCC。
在同一个 SCC 就说明可以在把它所在的一个偶环的边都反一下，显然这样做最大流不变。
例题：
- [[HAOI2017]新型城市化](https://www.luogu.com.cn/problem/P3731)
---
# 最小割
>最大流=最小割
## 通常解决的问题模型——集合划分
（又叫“文理分科”模型）
代价形如这样：第 $i$ 个物品在 $A$ 集合的代价为 $a_i$，在 $B$ 集合的代价为 $b_i$；两个物品 $(i_k,j_k)$ 如果 $i_k$ 和 $j_k$ 不在同一集合会产生 $w_k$ 的代价。
那么建立原点 $S$ 表示集合 $A$，建立原点 $T$ 表示集合 $B$。
对于每个物品 $i$，$S$ 向 $i$ 连一条流量为 $b_i$ 的边，割掉就表示 $i$ 在 $B$；同理 $i$ 向 $T$ 连一条流量为 $a_i$ 的边。
然后对于每对 $(i_k,j_k)$，$i_k$ 向 $j_k$ 并且 $j_k$ 也向 $i_k$ 连，容量都为 $w_k$。
还有些特殊的，可以参考例题。
例题：
- [P4313 文理分科](https://www.luogu.com.cn/problem/P4313)
- [AGC038 F - Two Permutations](https://atcoder.jp/contests/agc038/tasks/agc038_f) -> [题解](https://www.luogu.com.cn/blog/froggy/agc038-solution)
## 可行边与必须边
（注意和二分图中的进行区分）
先跑个最大流。无论 $(u,v)$ 是可行边还是必须边，它都必须**满流**。
如果不满流显然没必要割掉这条边。
$(u,v)$ 是可行边（包含在**某个**最小割的方案中）当且仅当：残量网络中 $u$ 不能到 $v$（即：$u$ 和 $v$ 不在同一个 SCC）。
证明：由于 $(u,v)$ 满流所以残量网络上一定有边 $(v,u)$。如果 $u$ 能到 $v$，那么把 $u\rightarrow v\rightarrow u$ 这个环的边都反一下，发现最大流不变但是 $(u,v)$ 这条边就不满流了。
$(u,v)$ 是必须边（包含在**所有**最小割的方案中）当且仅当：残量网络中 $S$ 能到 $u$ 且 $v$ 能到 $T$（即：$u$ 和 $S$ 在同一个 SCC，$v$ 和 $T$ 在同一个 SCC）。
证明：如果 $(u,v)$ 是必须边，那么显然 $(u,v)$ 的流量增大会导致最大流增大。显然 $S$ 能到 $u$ 且 $v$ 能到 $T$ 才能满足这一点。
例题：
- [P4126 [AHOI2009]最小割](https://www.luogu.com.cn/problem/P4126)
---
## 有上下界的网络流
咕咕咕