算法
有个建反向边的反悔思想。
FF 算法（指用 dfs 实现的 FF）
dfs 找增广路。
每次增广当前流量至少加 $1$，单次增广时间复杂度 $O(m)$。记 $F$ 为最大流，时间复杂度为 $O(Fm)$。
EK 算法
bfs 找到增广路。
时间复杂度为 $O(nm^2)$。
下面是证明。
每次增广后 $s$ 到除 $s$ 外每个点的最短路单调不降。
反证法，记 $d_u$ 为原最短路，$d’_u$ 为增广后的最短路，假设存在点 $u$ 满足 $d’_u<d_u$ 取 $d’_u$ 最小的点作为 $u$。
设增广后的最短路径形如 $s \leadsto x \to u$。那么 $d’u=d’x+1$。
此时 $(x,u) \notin E$，否则 $d_u \le d_x+1 \le d’_x+1 = d’_u$ 矛盾。
那么 $(x,u)$ 是增广后的反向边，即 $(u,x) \in E$。有 $d_u+1=d_x \le d’_x = d’_u-1$，即 $d_u \le d’_u-2$ 矛盾。
记一次增广流量等于增广流量的边为关键边，那么每条边最多成为 $\frac{n}{2}-1$ 次关键边。
若 $(u,v)$ 作为关键边，其再次出现需要 $(v,u)$ 作为关键边。那么 $ d_u = d_v-1 \le d’_v-1 = d’_u-2 $，而 $d$ 最小为 $1$ 最大为 $n-1$，最多出现 $\frac{n}{2}-1$ 次。
那么总增广次数为 $O(nm)$，单次增广时间复杂度 $O(m)$，总时间复杂度 $O(nm^2)$。
dinic
对于一般网络，时间复杂度为 $O(n^2m)$。
对于容量为 $1$ 的网络，时间复杂度为 $O(m\min(n^{\frac{2}{3}},\sqrt{m}))$。
对于单位网络，即满足 $\min(d_i^{in},d_i^{out}) \le 1$ 且容量为 $1$ 的网络，时间复杂度为 $O(m\sqrt{n})$。
增广轮数为 $O(\sqrt{\sum_{i}\min(d_i^{in},d_i^{out})})$。
下面是证明。
每次增广后到 $t$ 的最短路单调不减。
同理可证。
dinic 算法每次增广后 $s$ 到 $t$ 的最短路单调递增。
只需证明不相等，反证法，假设增广后最短路单调递增。
那么一定存在一条边 $e \notin E$，否则会被增广。那么 $d \ge d’+2$ 矛盾。
对于一般图，dinic 算法时间复杂度为 $O(n^2m)$。
会增广 $O(n)$ 轮，每轮增广会增广 $O(m)$ 次，每次增广时间复杂度 $O(n)$（分层图），总时间复杂度 $O(n^2m)$。
记 $S=\sum_{i}\min(d_i^{in},d_i^{out})$，那么增广轮数为 $O(\sqrt{S})$。
若增广超过 $O(\sqrt{S})$ 轮，那么之后的增广路长度 $>\sqrt{S}$。
将达到终态需要增广的路径提出来，对每个点分别考虑可得其总长度 $\le S$，那么路径数为 $O(\sqrt{S})$，则接下来至多增广 $O(\sqrt{S})$ 轮。
边容量为 $1$ 的网络，增广轮数为 $O(\sqrt{m})$。
$S=m$。
边容量为 $1$ 的网络，增广轮数为 $O(n^{\frac{2}{3}})$。
记 $s_i$ 为与 $s$ 最短距离为 $i$ 的点的个数，记 $d$ 为 $s$ 到 $t$ 的最短距离，记 $F$ 为最大流，有 $F \le s_is_{i+1} \le (\frac{s_i+s_{i+1}}{2})^2(i=0,1,…,d-1)$。
而 $\sum_{i=0}^{d-1} \frac{s_i+s_{i+1}}{2} < n$，故 $F < \frac{n^2}{d^2}$。
还有个增广轮数 $\le d$ 的限制，那么当 $d \le n^{\frac{2}{3}}$ 时，增广轮数为 $O(n^{\frac{2}{3}})$，当 $d > n^{\frac{2}{3}}$ 时，增广轮数为 $O(n^{\frac{2}{3}})$。
边容量为 $1$ 的网络，单次增广的时间复杂度为 $O(m)$。
每条边至多遍历一次。
单位网络的增广轮数为 $O(\sqrt{n})$。
$S=O(n)$。
最大流最小割定理
即 最大流 $=$ 最小割。
最大流 $\le$ 最小割，只需证明最大流 $\ge$ 最小割。
只需证明存在一个流等于一个割即可，最终的残余网络显然符合条件。
其实是对偶。
例题
1.二分图最大匹配
记 $X,Y$ 分别为左右部点。
$\forall x \in X,(s,x,1)$。
$\forall y \in Y,(y,t,1)$。
$\forall (x,y) \in E,(x,y,1)$。
2.Matrix Decompressing
求出每行每列的和。将每个点的初始值设为 $1$，范围转化为 $0-19$。
将每行每列视为一个点。对原图中点 $(x,y)$ 建 $(x,y,19)$。从 $s$ 向每行连容量为当前行的和的边，列向 $t$ 连边。
跑最大流即可保证行和列均满足和的条件。
每个点的值即为边的流量 $+1$。
3.有负圈的费用流
由于有负环，基于最短路的费用流无法直接处理。
强制让负权边满流，但是这样会使有的点的入流与出流不等。
若点的入流大于出流，则需要流出一些流，反之则需要流入一些流。用网络流处理。
建立虚拟源汇点 $s,t$。记 $in_i$ 为点 $i$ 的入流减出流，
$in_i > 0$ 连边 $(s,i,in_i,0)$。
$in_i < 0$ 连边 $(i,t,-in_i,0)$。
以虚拟源点跑一次费用流那么原图流量平衡（这叫做可行流），再跑费用流求解。
4.有源汇上下界最大流
先强制流满每条边的下界，跑可行流。若不存在可行流（没有满流）则无解。
特别的，由于原图中的源点、汇点入流不一定等于出流，所以连边 $(t,s,\infty)$。
跑出可行流后，将 $t$ 到 $s$ 的边删去，再跑一次最大流。可行流加最大流即为答案。
5.文理分科
每个同学要么选文科要么选理科，该问题为划分问题，用最小割来解决。
对于每个同学，从 $s$ 连一条容量为选文科所得满意值的边，向 $t$ 连一条容量为选理科所得满意值的边，该同学最终与 $s$ 相连即为选了文科，反之理科。
对于选相同科目的满意值（举都选文科为例），新建一个节点 $i$ 代表以 $i$ 为中心的五位同学
从 $s$ 连一条容量为全选文科所得满意值的边，向五位同学分别连一条容量为 $\infty$ 的边。
表示若要获得全选文科所得的满意值，则五位同学的理科边（容量为选理科所得满意值的边）都要割断。
最大满意值即为剩下的边的边权，用满意度之和减去最小割即可。
6.骑士共存问题
仍可看成划分问题，即每个位置选或不选。限制为选择某个点则周围的点强制不选。
为了加边满足该限制，一个点与相邻的点的方向应是相反的，即被划分到 $s$ 的含义不同。
没有奇环，点被合法地分成了两类，对应原图黑白染色的结果。
建图时流量为 $0$ 的边可以省去，这样就是主流的建图方式了。
此题的 $\infty$ 可以视为 $1$，发现建图与二分图最大匹配相同，事实上本题就是求二分图最大独立集。
7.太空飞行计划问题
考虑一般的问题，即最大权闭合子图。
看成划分问题，需要满足一个点被选，那么它的邻点强制被选。
由于点权有负数，不能直接建图，先加上点权的绝对值即可。
详细解释。
对于点权为正的，连边为 $val,0$，答案为 $val-割$（最小割满足保留边的权值最大）。
对于点权为负的，开始连边 $val,0$，答案为 $val-割$，由于 $val$ 为负，考虑连边 $0,-val$，答案为 $val-(割+val)=0-割$。
8.Hard Life
通过01分数规划求解。二分 $\frac{|E|}{|V|}$（记为$g$）。要判断是否有
即求出当前 $|E|-g|V|$ 的最大值。
二分的下限为 $\frac{1}{n}$ ，上限为 $m$ ，两个不同的密度差最少为 $\frac{1}{n^2}$ 这决定了精度。
我们使用最小割求解$\left|E\right|-g\left|V\right |$ 的最大值。
将无向边拆为两条有向边。
记 $V$ 为与 $s$ 相连的点集，其补集为 $V’$，$C[V,V’]$ 为起点在 $V$，终点在 $V’$ 的边的个数。则
这样就将边的信息转化为点的信息了。
考虑如何凑出原式。最小割为下面三种边的容量和
$s \to V’$
$V \to t$
$V \to V’$
对于边三，可以将原图中的边的容量设为 $1$，得到 $C[V,V’]$。对于边二，设容量为 $2g-out_i$，但是这样会使有的容量为负，加一个 $\Delta$ 即可（用 $m$）。这样会多算 $|V|m$，让边一容量为 $m$。
最小割即为
所以 $m-gn=\frac{(mn-\texttt{maxflow})}{2}$。
9.最小路径覆盖问题
将每个点看作一条路径，每次可以首尾合并两条路径。
将每个点拆为 $in,out$，对于边 $u \to v$，连边 $(out_u,in_v,1)$。
跑二分图最大匹配即可。
对于允许链相交的问题，先跑传递闭包，再跑二分图最大匹配。
10.[CTSC2008] 祭祀
一个 DAG 中最长反链的大小，等于最小链覆盖的大小。
由鸽巢原理可知，最长反链 $\le$ 最小链覆盖。只需构造方案即可。
将原图传递闭包后拆点建出二分图，标记最大独立集中的点，若原图中点的入点与出点均被标记，则该点属于最长反链。
一个点的入点与出点均在独立集中，反映到原图上，则它与其他反链上的点均未直接相连，所以选出的点一定为反链。
由于最小链覆盖 $=n-$ 最大匹配数、最大独立集 $=2n-$ 最大匹配数，所以最小链覆盖 $=$ 最大独立集 $-n$。
那么只要每个点至少有一个入点或出点被标记，则选出的方案为最大反链。可以反证法证明。
若点 $i$ 的入点（$i’$）与出点（ $i’’$ ）均未被标记，则必有 $j’’$ 与 $i’$ 相连，$k’$ 与 $i’’$ 相连，且 $j’’,k’$ 均被标记。
由于原图为 DAG 所以 $j,k$ 不为同一点。
由于先进行了传递闭包，所以若 $j \to i$ 且 $i \to k$ ，则必有 $j \to k$ ，即 $j’’$ 与 $k’$ 相连，此时不满足独立集的条件，故该情况不成立。
对于第三问，枚举每个点，将与它相连的点删去，再计算最长反链。若此时的最长反链 $=ans-1$，则该点可选，反之不可选。
11.最长k可重区间集问题
限制是 $\le k$ 考虑网络流，建图看看得了，感觉就是妙手偶得啊，不会讲。
12.[CTSC1999] 家园/星际转移问题
太空船只可容纳 $h$ 个人，即太空船最多容纳 $h$ 个人，可以发现是容量的定义，用网络流求解
由于太空船移动的特殊性和极小的数据范围，我们可以想到枚举答案、动态加边，直到 $k$ 个人运出输出此时的答案。
每次在可以上一次的残量网络上跑最大流。
对于无解的判断，如果地球和月球无法通过太空船相连即无解，用并查集判断。
13.[NOI2010] 海拔
先贪心一下，最后的图一定为一片 $1$ 与一片 $0$。
所以该题就转化为了最小割问题，但是用最大流求最小割会超时。
图为平面图，我们可以将平面图最小割转化为对偶图最短路。
具体地，将平面图中每一个平面看作一个节点，将两个平面之间的邻边转化为两个节点之间的边。
对于最上侧和最右侧的边，将它看作 $s$ 与所在平面的边。
对于最下侧和最左侧的边，将它看作 $t$ 与所在平面的边。
例如，$i$ 与 $j$ 平面上下相邻，对于中间从西到东的邻边，将其转化为 $i \to j$。
因为若该边计入答案，则西边的节点为 $0$ ，东边的节点为 $1$，所以转化为从上到下的边
将其他情况都推一遍，可以发现是将原图中的边顺时针旋转 $90$ 度。
14.[AHOI2009] 最小割
满流且两端点不在同一连通分量的边为可行边。
满流且两端点分别在 $s,t$ 的强连通分量的边为必须边。
将跑任意最大流后得到的残量网络缩点，得到一张 DAG，DAG 上任意紧的割都是原图的最小割。
杂题
1.A Plug for UNIX
类似于二分图最大匹配建图
对于插座 $i$ 连 $(i,t,1)$。
对于插头 $i$ 连 $(s,i,1)$。
对于转换器 $u \to v$ 连 $(u,v,\infty)$。
跑最大流即可。
2.方格取数加强版
3.[SCOI2007] 修车
等待相当于每次从头开始走一遍。费用流解决。
4.[NOI2008] 志愿者招募
类似最小路径覆盖问题，容量为 $\infty-a_i$ 即可。
5.Help Little Laura
给你一个有向图，每条边的权值为 $len \times x-y$ ，找一些不相交的环，使得权值和最大。
若将每条边的流量定为 $1$ ，则一个合法的涂色方式中每个点的入流与出流相等，跑可行流即可。
还可以每次用 spfa 找一个负环增广。
6.Euler Circuit
由于欧拉回路中每条边只能经过一次，所以不能简单地将无向边拆为有向边。
我们需要找一个将无向边定向的方案，使原图存在欧拉回路。那么需要满足每个点的入度减出度为 $0$。
先随意将无向边定向，记 $in_i$ 为点i的入度减出度。
将 $u \to v$ 的无向边取反则 $in_u+=2,in_v-=2$，相当于流量从 $u$ 流入 $v$。
按残量网络建图，再跑欧拉回路即可。
7.Chips Challenge
由于每一行与每一列的芯片数相同，可以将行与列看成一个点。
对于 $.(i,j)$，连 $(i,j,1,1)$。
对于 $C(i,j)$，由于要强制选择，连 $(i,j,1,\infty)$。
所以题目就转化为一个最大费用可行流问题，除去 $\infty$ 的费用和即为添加的部件个数。
再考虑 $A/B$ 这个限制。由于 $N$ 较小，可以考虑枚举行或列最多的部件数 $k$。拆点，连 $(i’,i’’,k,0)$。
如果 $当前C的个数 \times A>=Bk$ 则合法，取最大值即为 $ans$。
对于最大费用可行流问题，我们先将边权取反，转化为最小费用可行流。
自己推一下即可得到如下连边方式
$(i’,i’’,k,0)$。
$(s,i’,maxl_i,0)$。
$(i’’,t,maxh_i,0)$。
对于$.(i,j)$，连 $(j’,i’’,1,1)$，此处连边是为了删边，由于 $C$ 连的边不需要删，所以可不连该边。
8.[ZJOI2011] 营救皮卡丘
9.无限之环
10.[WC2007] 剪刀石头布
每个点的贡献可以写成等差数列形式，依次连边即可。
zkw 费用流
貌似就是倒着跑 spfa 的 dinic？
最大流唯一性判定
跑出残量网络，相当于判断混合图是否有环，将无向边缩点跑拓扑排序即可。
参考
On finding a maximum flow in a network with special structureand some applications 1
某课件