最大流
对于网络 \(G = (V, E)\) ，给每条边指定流量，得到合适的流 \(f\) ，使得 \(f\) 的流量尽可能大。此时我们称 \(f\) 是 \(G\) 的最大流。
Dinic
算法思想
考虑在增广前先对 \(G_f\) 做 BFS 分层，即根据结点 \(u\) 到源点 \(s\) 的距离 \(d(u)\) 把结点分成若干层。令经过 \(u\) 的流量只能流向下一层的结点 \(v\) ，即删除 \(u\) 向层数标号相等或更小的结点的出边，我们称 \(G_f\) 剩下的部分为层次图（Level Graph）。形式化地，我们称 \(G_L = (V, E_L)\) 是 \(G_f = (V, E_f)\) 的层次图，其中 \(E_L = \left\{ (u, v) \mid (u, v) \in E_f, d(u) + 1 = d(v) \right\}\) 。
如果我们在层次图 \(G_L\) 上找到一个最大的增广流 \(f_b\) ，使得仅在 \(G_L\) 上是不可能找出更大的增广流的，则我们称 \(f_b\) 是 \(G_L\) 的阻塞流（Blocking Flow）。
定义层次图和阻塞流后，Dinic 算法的流程如下。
-
在 \(G_f\) 上 BFS 出层次图 \(G_L\) 。
-
在 \(G_L\) 上 DFS 出阻塞流 \(f_b\) 。
-
将 \(f_b\) 并到原先的流 \(f\) 中，
-
重复以上过程直到不存在从 \(s\) 到 \(t\) 的路径。
注意到在 \(G_L\) 上 DFS 的过程中，如果结点 \(u\) 同时具有大量入边和出边，并且 \(u\) 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 \(u\) 这个局部的时间复杂度最坏可达 \(O(|E|^2)\) 。为避免这一缺陷，如果某一时刻我们已经知道边 \((u, v)\) 已经增广到极限（边 \((u, v)\) 已无剩余容量或 \(v\) 的后侧已增广至阻塞），则 \(u\) 的流量没有必要再尝试流向出边 \((u, v)\) 。据此，对于每个结点 \(u\) ，我们维护 \(u\) 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。
Dinic 算法的时间复杂度是 \(O(|V|^2|E|)\) ，然而绝大部分情况跑不满。
1.在单位容量的网络上，Dinic 算法的总时间复杂度是
\(O(|E| \min(|E|^\frac{1}{2}, |V|^{\frac{2}{3}}))\) 。
在单位容量的网络上，如果除源汇点外每个结点 \(u\) 都满足 \(\mathit{deg}_{\mathit{in}}(u) = 1\) 或 \(\mathit{deg}_{\mathit{out}}(u) = 1\) ，Dinic 算法的总时间复杂度是
\(O(|E||V|^{\frac{1}{2}})\) 。对于二分图最大匹配问题，我们常使用 Hopcroft–Karp 算法解决，而这一算法实际上是 Dinic 算法在满足上述度数限制的单位容量网络上的特例。
ISAP
和 Dinic 算法一样，我们还是先跑 BFS 对图上的点进行分层，不过与 Dinic 略有不同的是，我们选择在反图上，从 \(t\) 点向 \(s\) 点进行 BFS。
执行完分层过程后，我们通过 DFS 来找增广路。
增广的过程和 Dinic 类似，我们只选择比当前点层数少 \(1\) 的点来增广。
与 Dinic 不同的是，我们并不会重跑 BFS 来对图上的点重新分层，而是在增广的过程中就完成重分层过程。
具体来说，设 \(i\) 号点的层为 \(d_i\) ，当我们结束在 \(i\) 号点的增广过程后，我们遍历残量网络上 \(i\) 的所有出边，找到层最小的出点 \(j\) ，随后令 \(d_i \gets d_j+1\) 。特别地，若残量网络上 \(i\) 无出边，则 \(d_i \gets n\) 。
容易发现，当 \(d_s \geq n\) 时，图上不存在增广路，此时即可终止算法。
和 Dinic 类似，ISAP 中也存在 当前弧优化。
而 ISAP 还存在另外一个优化，我们记录层数为 \(i\) 的点的数量 \(num_i\) ，每当将一个点的层数从 \(x\) 更新到 \(y\) 时，同时更新 \(num\) 数组的值，若在更新后 \(num_x=0\) ，则意味着图上出现了断层，无法再找到增广路，此时可以直接终止算法（实现时直接将 \(d_s\) 标为 \(n\) ），该优化被称为 GAP 优化。
/!!!!!!!!!!!
2.最小割问题：对于网络 \(G = (V, E)\) ，找到合适的 \(s\) - \(t\) 割 \(\{S, T\}\) ，使得 \(\{S, T\}\) 的容量尽可能小。此时我们称 \(\{S, T\}\) 是 \(G\) 的最小割。
3.最小费用最大流问题：在网络 \(G = (V, E)\) 上，对每条边给定一个权值 \(w(u, v)\) ，称为费用（cost），含义是单位流量通过 \((u, v)\) 所花费的代价。对于 \(G\) 所有可能的最大流，我们称其中总费用最小的一者为最小费用最大流。