流流。
概念
网络流：一个算法。
网络：一张有向图，上面有源点和汇点。（水管线路）
弧：网络上的一条边。下文简称边。（水管）
流量：一条边的一个属性。记作 $f(x,y)$。可以为负。（水管运输水量）
容量：一条边的另一个属性。记作 $c(x,y)$。（水管最大流量）
源点：起点。（水厂）
汇点：终点。（废水回收站？）
容量网络：每条边都有容量的网络。（规划图）
流量网络：每条边都有容量的网络。（计划）
残留容量：对边来说，残留容量 = 容量 - 流量。
残量网络：每条边都有残留容量的网络。（水管冗余）
性质
容量限制
不是人话：$\forall (x,y) \in E,f(x,y) \leq c(x,y)$。
人话：流量不超过容量。
流量守恒
不是人话：$\forall x \in V$ 且 $x \neq S$ 且 $x \neq T$，$\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v) \in E} f(x,v)$。
人话：吃进去多少就吐出来多少。
斜对称
不是人话：$\forall (x,y) \in E,f(y,x) = -f(x,y)$。
人话：正着是多少反着就是负多少。
最大流
概念
网络的流量：在某个流量网络中汇点收到的流量。（回收站收到的水量）
最大流：网络的流量的最大值。（回收站最多能收到的的水量）
最大流网络：使得网络的流量最大的流量网路。（最优计划线路图）
算法
EK 增广路
概念
增广路：一条在残量网络上从 $S$ 到 $T$ 的路径，且路径上所有残留容量均为正。（一条可以抵达的路线）
增广路定理：流量网络达到最大流当且仅当残量网络没有增广路。（都到不了当然无法获得更大流量）
算法
(1) 在残量网络上从 $S$ 点出发跑 bfs，找到边数最小的增广路，并记录各边残留容量的最小值。若找不到增广路，结束。
(2) 更新答案和残量网络。
(3) 回到 (1)。
理解
残量网络的更新需要同时更新正向边 $-F$ 和反向边 $+F$，这是为了给算法一些“反悔”的机会，若流量流经反向边则代表正边撤回一些流量去往新方向。
时间复杂度
每条边被增广的次数是 $O(n)$ 的，总计增广 $O(nm)$ 次，一次 bfs 增广为 $O(m)$，总复杂度 $O(nm^2)$。
实现
由于需要快速寻找反向边，链式前向星一般来说比邻接表更好用。
但是！作为 vector 神教的一员，我们不能扔下邻接表不管！
嘿嘿那我退出 vector 神教了。
我们在每条边直接记录反向边的编号即可做到 $O(1)$ 查询。代价是空间常数有点大。
真的不是我的链前写不好，你一定要相信我！
Dinic
算法
(1) bfs 跑出分层图。
(2) 根据层次进行多次 dfs 遍历残量网络，一次找到一条增广路并进行更新。
优化
多路增广
一次 bfs 可以找到 $1 \sim m$ 条增广路，但 dfs 的更新没有优化，导致复杂度还是很爆。
我们在 dfs 的时候对于每个点 $x$，记录 $x \rightarrow T$ 的路径上已经用掉的流量，如果已经达到上限就不再遍历搜索其他边，直接返回已用去的流量。
到达汇点时，则返回收到的流量并进行更新。
当前弧
在一个分层图中，已经处理结束的边就没用了，因为我们是依次遍历每个出发点，所以可以记录上一次推到哪里，继续向后。
时间复杂度
也就 $O(n^2m)$。但是常数超级小，甚至能通过 $10^5$。
ISAP & HLPP
Dinic 已经很快了，拿更多的码量去换不太明显的效率提升实在有点亏。所以， 我不学！
最小割
概念
割集：一个源点为 $S$，汇点为 $T$ 的网络划分为两个点集 $s$ 和 $t$，且 $S \in s,T \in t$，于是所有边 $(x,y)$ 满足 $x \in s,y \in t$ 构成的集合成为割集。（切割后网络不连通）
最小割：容量和最小的割集。
求法
根据最大流最小割定理，原图最大流即等于最小割。
Ohh 这么奇幻。
费用流
概念
单位流量费用：单位费用。一条边的费用 $=$ 流量 $\times$ 单位费用。记作 $w(x,y)$。
最小费用最大流：在所有最大流网络中，费用最小的。（不应该叫最大流最小费用吗）
算法
SSP
其实是上面两个算法的变种。
我们复制 EK 的内容并稍作修改：
(1) 在残量网络上从 $S$ 点出发跑 bfs SPFA，找到 边数 单位费用和最小的增广路，并记录各边残留容量的最小值。若找不到增广路，结束。
(2) 更新答案和残量网络。
(3) 回到 (1)。
就好了。
实现
注意反向边的单位费用是 $-w(x,y)$。
但是吧，
- 它死了
万一良心出题人卡你怎么办。
不知道你是否听过 Johnson 全源最短路。这个算法通过一次 SPFA 重新标注边权使得 Dijkstra 可以运行。
我们可以利用类似的 Primal-Dual 原始对偶算法，每次增光前，先跑一遍 SPFA，然后重新标注边权。
时间复杂度
我不会。长大后再知道是 $O(nm|f|)$ （朴素）或 $O(m \log m |f|)$ （原始对偶） 吧。