网络流
内容主要为自己对网络流的一些理解和一些典例。
一些约定：
- s 为源点，t 为汇点
- 对于集合 $S,T,T\subseteq S$，约定 $S-T$ 为从 $S$ 中删掉 $T$ 中每个元素之后的集合
- 网络流图为 $G=(V,E)$，边 $(u,v)$ 容量记为 $c_{u,v}$
最大流最小割定理和增广路定理
这两个定理是网络流问题的核心定理。
内容
最大流 = 最小割。
残量网络中不存在增广路是当前流为最大流的充要条件。
证明
若当前流为最大流，显然不存在增广路。
若当前流等于某个割，显然当前流为最大流，且该割为最小割。
若不存在增广路，我们证明当前流等于一个割。
令 $S=\{v,\exist\ p_{s,v}\}$，$S$ 即 $s$ 在残量网络中能到达的点的集合。令 $T=V-S$。显然 $(S,T)$ 是一个割，对于当前残量网络 $G’=(V,E’)$，一定有 $\forall x \in S,\forall y\in T$，边 $(x,y)$ 满流，否则 $y\in S$。容易证明当前流恰好为 $S$ 到 $T$ 的所有边的容量和，也就是割的大小。因为此时原图 $S$ 到 $T$ 所有的边流量为容量，$T$ 到 $S$ 的边流量为 $0$，所以流量为 $S$ 到 $T$ 的边的流量之和，也就是割 $S,T$。
算法
Dinic
考虑对残量网络 bfs 分层，强制流量只能流向下一层，再进行一次 dfs，求限制下所有的增广路，搞定。
复杂度 $O(n^2m)$
每次增广复杂度为 $O(nm)$，共计增广 $n$ 次，因为每次增广都会让 $dep[t]$ 增加 1。
每次增广的复杂度不是很好证，但加了当前弧优化其实就很松。
代码记在脑子里了，不放了。
ISAP
咕咕咕
HLPP
咕咕咕
费用流相关
一般指最小费用最大流，暂时没啥感觉，不写。
最小割
非常常见的一个网络流模型应用。
核心思想
通过构造一个图的割到决策方案的映射，其中决策必须可拆分计算，求出最小的代价，一般来说决策的限制如果比较奇怪就应该考虑最小割。
常用于规划 $0/1$ 独立贡献决策问题。
适用条件
- 不能存在负容量边权，我不知道有没有人会，反正我是不会。
1.最大闭合权子图问题
给定一张有向图，点带权（权可以为负），选一个子图出来，要求如果 $u$ 选了那如果存在 $(u,v)$，那 $v$ 也要选。求最大权值和。
决策贡献独立，决策类型为 0/1。应该可以最小割。令割中与 $s$ 同集合的点为选择的点，与 $t$ 同一个集合的点为未选择的点。那么每个点应该和 $t$ 连一条流量为权值的相反数的边，代表选它的代价，再对于每条 $(u,v)$ 从 $u$ 向 $v$ 连一条 inf 边,代表选了 $u$ 不选 $v$ 的代价。考虑这张图的一个最小割，它必然不会包含 inf 边，也就是说，我们选了 $u$ 在 $s$ 中一定会让 $v$ 在 $s$ 中，所以一定合法。然后发现原问题的每一个答案都可以和图上的一个不含 inf 边的割一一对应，故最小割就是原问题的答案的相反数。
这张图有负数，不行，所以考虑先默认选所有正数。那么选负数的代价为相反数，不选正数的代价为本身。
那么应该从 $s$ 向正权点连边，从负权点向 $t$ 连边，最后对于 $(u,v)$ 从 $u$ 向 $v$ 连 inf 边即可。