发现其实整理不完所有内容，干脆把所有不会的记了算了 qwq。
基础定义
网络 \(G = (V, E)\) 是一张有向图，其中的边 \((x, y) \in E\) 都有一个权值 \(c(x, y)\)，称为 容量。特别的，对于 \((x, y) \notin E\) 可以认定 \(c(x, y) = 0\)。
与一般有向图的区别在于，\(\exist s, t \in E\) 称为网络的 源/汇点，满足 \(s\) 只有出边、\(t\) 只有入边。可以认为 \(s\) 拥有有 无限的流。当然，一部分特殊的网络可能 有多个甚至没有 源汇点。
对于网络 \(G\)，流 （流量）\(f\) 指一个 \(E\) 到整数（实数）集的函数，（人话就是边的 实际流量，）满足：
- 容量限制：对于每条边，实际流量不超过其容量，\(0 \le f(x, y) \le c(x, y)\)；
- 流量守恒：除源汇点外，所有节点不额外储存流，流入总量等于流出总量，\(\forall x: \sum_{y \in V} f(y, x) = \sum_{y \in V} f(x, y)\)；
- 斜对称性：\(f(x, y) = -f(y, x)\)，这个相当于定义了负流。
对于流 \(f\)，记其流量为 \(\lvert f \rvert\)。
同时定义 可行流 为一条从源点到汇点的合法路径；残量 为每条边的 \(c(x, y) - f(x, y)\)。上述三种量构成的网络分别定义为 容量网络、流量网络、残量网络。特别的，残量网络上的可行流又叫作 增广路。
以及，对于点集的一个划分 \(\{S, T\}\) 满足 \(s \in S, t \in T\)，称之为 割，并定义其容量为 \(\left\| \{S, T\} \right\| = \sum_{x \in S, y \in T} c(x, y)\)。
最大流最小割定理
证明 FF 增广的正确性，等价于证明 最大流最小割定理，即一张网络的 最小割容量 等于其 最大流流量。下面从一个引理出发证明这个定理。
引理：对于网络 \(G\) 与任意流 \(f\)、割 \(\{S, T\}\)，有 \(\lvert f \rvert \le \left\| \{S, T\} \right\|\)。其中，取等号当且仅当 \(\forall x \in S, y \in T: f(x, y) = c(x, y), f(y, x) = 0\)。
Proof：
定义点 \(x\) 的 净流量 为 \(f(x) = \sum_{y \in V} f(x, y) - f(y, x)\)，容易有 \(x \neq s, t \Rightarrow f(x) = 0\)。则：
\[\begin{aligned} \lvert f \rvert &= f(s) \\ &= \sum_{x \in S} f(x) \\ &= \sum_{x \in S} (\sum_{y \in V} f(x, y) - f(y, x)) \\ &= \sum_{x \in S} (\sum_{y \in S} f(x, y) - f(y, x) + \sum_{y \in T} f(x, y) - f(y, x)) \\ &= \sum_{x \in S} (\sum_{y \in T} f(x, y) - f(y, x)) + \sum_{x \in S} \sum_{y \in S} f(x, y) - f(y, x) \\ &= \sum_{x \in S} (\sum_{y \in T} f(x, y) - f(y, x)) \\ &\le \sum_{x \in S} \sum_{y \in T} f(x, y) \\ &\le \sum_{x \in S} \sum_{y \in T} c(x, y) \\ &= \left\| \{S, T\} \right\| \end{aligned} \]取等号的两个条件分别对应倒数第一、第二个小于等于号。（莫名感觉这些加入无用量恒等变形证明好抽象……）
考虑证明两种状态均可取到来证明原定理。考虑一张无法继续增广的剩余网络，记 \(s\) 可到达的集合为 \(S\)，以及 \(T = V \setminus S\)，显然 \(\{S, T\}\) 是一个 割（因为 \(t \in T\)）且 \(\left\| \{S, T\} \right\| = 0\)。于是 \(\forall x \in S, y \in T\)：
- 若 \((x, y) \in E\)，则 \(c'(x, y) = 0 = c(x, y) - f(x, y)\)，有 \(f(x, y) = c(x, y)\)；
- 反之若 \((y, x) \in E\)，则 \(c'(x, y) = 0 = c(x, y) - f(x, y) = 0 - f(x, y) = f(y, x)\)，有 \(f(y, x) = 0\)。
写一遍似乎没难么难理解证明过程了，最小割也就不用讲了。怎么感觉这部分和 OI Wiki 长得一样？
Dinic 的复杂度
当前弧优化 是 Dinic 的复杂度保证，而 多路增广 是 Dinic 的常数优化。
对于 一般网络，复杂度应为 \(\mathcal{O}(n \times n m)\)，因为 层数单调 总计增广 \(\mathcal{O}(n)\) 次，然后每次 DFS 复杂度 \(\mathcal{O}(n)\) 并且 至少减掉一条边，有单次增广 \(\mathcal{O}(n m)\)。
同时也有关于 值域 的增广上界。设 \(S = \sum \min(inC_{i}, outC_{i})\)，如果在第 \(\sqrt{S}\) 轮增广之前就已经结束的话，不用管；否则此时的 增广路长度 不小于 \(\sqrt{S}\)，则会存在 某两层之间形成的割 大小不超过 \(\sqrt{S}\)，也就是最大流不超过 \(\sqrt{S}\)，最多再流 \(\sqrt{S}\) 次。
对于 单位容量网络，复杂度应为 \(\mathcal{O}(\min(m^{\frac{1}{2}}, n^{\frac{2}{3}}) \times m)\)，单轮增广的 \(m\) 是由于每条边只被走一次，增广轮数的 \(n^{\frac{2}{3}}\) 则需要类比上面的值域分析：假设已经进行了 \(2 n^{\frac{2}{3}}\) 轮增广，则最坏情况下每层平均 \(\dfrac{1}{2} n^{\frac{1}{3}}\) 个节点，最多有 \(n^{\frac{2}{3}}\) 曾包含点数不小于 \(\dfrac{1}{2} n^{\frac{1}{3}}\) 个节点。于是至少有相邻的俩层点数都不超过 \(n^{\frac{1}{3}}\)，最坏情况下形成一个大小为 \(n^{\frac{2}{3}}\) 的割，也就是最大流不超过 \(n^{\frac{2}{3}}\)，总共进行 \(\mathcal{O}(n^{\frac{2}{3}})\) 次增广。
单位容量网络 不等价于 单位网络，单位网络在其基础上要求 \(in_{i} = 1 \lor out_{i} = 1\)，二分图 就是一种经典的单位网络。结合第二、三条不难的出其复杂度为 \(\mathcal{O}(m \sqrt{n})\)，或者 OI Wiki 上有个不太一样的证法。
最小割建模
问题是对于最小化的。
- 把一个物品当成一条 容量等于权值 的边，割这条边 代表选这个物品；
- 多个物品 不同时选，则把它们 串在同一条增广路上；同时建 容量为 \(\infty\) 的反向边