网络流部分结论性质及证明

最近做到了很多网络流的题，一眼都挺不一眼的，凭自己也只有几道可以想到性质，但知道网络流相关知识之后就都是简单题了。

以下所有的证明都偏口胡，但有一定程度上的严谨性。

设情景下的最大流流量为 \(|F|\)。

称某个最大流方案中这条边流量所构成的流网络为使用流网络。

称流网络中每条边的容量减去某个最大流方案中这条边流量所构成的流网络为残量网络。

最大流最小割定理

网络最大流等于有向图有源汇最小割。

比较显然。

\(s \to t\) 形成最大流网络的残量网络中 \(s,t\) 不可达，此时流量为 \(|F|\)，可知最小割 \(C \ge |F|\) ，因为至少要花 \(|F|\) 才可能将 \(s\to t\) 完全割开。

因为考虑如果将某些边的容量减去 \(c\)（\(C=\sum c\)），那么最大流最多减少 \(C\)。而割完任意一个割后最大流变为 \(0\)，说明 \(C \ge |F|\)。

证明 \(\exists C = |F|\) 可以考虑构造最小割，令 \(S\) 为残量网络中 \(s\) 可达点构成的点集，割去 \(S\) 在原流网络中指向 \(S\) 以外任意点的边。可以发现这些边在最大流方案中一定满流，否则这条边另外一端将出现在 \(S\) 中。因为 \(S\) 中任意一点在割完边后不可达 \(t\)，所以满足割，且割去的边权和为 \(|F|\)。

即证。

\(\textrm{Ford-Fulkerson}\) 增广路思想

这是部分最大流算法的思想。对于流网络任意边建立容量为 \(0\) 反向边，在剩余流量网络上一直找到增广路，并将路径上的边的容量减去这条路上的最小容量，反向路径加上最小容量。找不到增广路时停止。同时答案加上这个最小容量，最后即为最大流。

正确性证明非常简单。这样的增广路思想最后会找到一个可行流，且无法找到其他的增广路。所以有两点：1.可以构造出一个割，割的大小为这个可行流的流量，构造方案和原理见最大流最小割定理。记这个可行流为 \(|F'|\)，当前构造出的割为 \(C'\)，可知 \(|F'|\le |F|\le C \le C'\)，又因为 \(|F'|=C'\)，所以 \(|F'|=|F|=C=C'\)。

即证。

而且可以发现 \(\textrm{Ford-Fulkerson}\) 增广路思想的正确性和最大流最小割定理的正确性是等价的。

\(\textrm{Dinic}\) 时间复杂度

（比较糊）

实际上在增加弧优化后 \(\textrm{Dinic}\) 算法每轮增广的时间复杂度最多为 \(O(|V||E|)\)。

因为每一条路径上因为饱和（满流）最多会令 \(O(|V|)\) 个点的弧指向发生变化，且由 \(O(|V|)\) 个点形成的增广路找到，而最多只有 \(O(|E|)\) 条边在一轮中会同时饱和，所以复杂度为 \(O(|V||E|)\)。

而 \(\textrm{Dinic}\) 算法最多会执行 \(O(|V|)\) 轮。

为此拜读了王欣上《浅谈基于分层思想的网络流算法》 一文，太牛了薄纱其他证明。

上述结论是证明每轮建出的层次图中 \(t\) 的层次单调递增的必要条件，所以转而考虑证明后者。

令当前层次图为 \(G_f\)，且 \(t\) 在第 \(k\) 层。我们通过不同的层次将点划分为不交的点集，\(V_d\) 表示第 \(d\) 层的点形成的点集。然后考虑将当前剩余流量网络上边分为两类：

• \(E_1\) ，\(\forall (u,v)\in E_1 : u \in V_d,v\in{V_{d+1}}\)。实际上是层次图上真正使用的边。称一条在 \(E_1\) 中的边为 \(E_1\) 边，符号为 \(e_1\)。
• \(E_2\)，\(\forall(u,v)\in E_2:u\in V_x,v\in V_y,x>y\)。实际上是层次图未使用的边。称一条在 \(E_2\) 中的边为 \(E_2\) 边，符号为 \(e_2\)。

然后可知的是不存在其他类型的边，否则层次图 \(G_f\) 错误。

在移除阻塞流之后，\(G_f\) 中一定不存在通过最多 \(k\) 条 \(E_1\) 边就可从 \(s\) 到达 \(t\) 的路径。并且在将流量加给相当于是删去了一些 \(E_1\) 边，加入了一些 \(E_2\) 边。

因为不能直接走 \(k\) 条 \(E_1\)，所以最终 \(s\to t\) 的最短路径应该形如 \(e_1e_1e_1e_2e_2e_1e_2\cdots e_2e_1e_1e_1\) 这样交错地经过的，且 \(e_2\) 一定存在。所以实际上我们必须至少走 \(k\) 条 \(E_1\) 边才能到达 \(t\)，因为边的类型只有上述两种使得每次走 \(E_1\) 边当前点层次最多与上一个点相比增加 \(1\)，而 \(t\) 在第 \(k\) 层。又因为至少要走 \(1\) 条 \(E_2\) 边以及其对应的可能出现的 仅用来补齐 \(E_2\) 减去的层次的 \(E_1\)，所以可以得出每次 \(s \to t\) 的深度一定至少加 \(1\)，保持单调递增。

所以每轮建出的层次图中 \(t\) 的层次单调递增。

\(\textrm{Dinic}\) 算法最多执行 \(O(|V|)\) 轮，每轮时间复杂度最多为 \(O(|V||E|)\)。

所以 \(\textrm{Dinic}\) 算法的时间复杂度理论上界应该小于等于 \(O(|V|^2|E|)\)，且实际上可以构造出取等的图。

如何构造？

二分图相关问题

建立源汇点后的流网络的最大流=二分图最大匹配。

同时二分图最大匹配=二分图最小点覆盖=总点数-最大独立集点数=总点数-补图最大团点数

挺显然的不证了。

最大权值闭合图

可以转化成最小割。

设置源点 \(s\) 和汇点 \(t\)。若 \(u\) 点权值非负，则 \(s\) 向 \(u\) 连边，流量为该点点权；否则 \(u\) 向 \(t\) 连边，流量为该点点权的相反数。

对于每条在原图中的边 \(u \to v\)，\(u\) 向 \(v\) 连边，流量为 \(\infty\)。

记 \(i\) 点权为 \(a_i\)， \(sum=\sum_{a_i>0} a_i\)，然后考虑在流网络中求最小割。考虑割每条边的意义：割原图中的边，因为流量为 \(inf\)，所以不可割；割正权点与 \(s\) 的连边，相当于不选这个点，则减去这个点的权值；割负权点与 \(t\) 的连边，相当于选这个点，需要加上这个点的点权，即减去其对应边的容量。

于是 \(ans=sum-C\) ，其中 \(C\) 为割的边权之和。

所以最大权值时 \(C\) 最小，答案为 \(sum\) 减去最小割。

最小路径覆盖

拆点最大流求解。将每个点拆成入点和出点，考虑原图中的边在流网络上对应一条入点连向出点流量为 \(1\) 的边，发现最终变为一张二分图，而上述边是否满流可以对应原图中这两个点是否在一个覆盖的路径中，可以发现路径覆盖=点数-在同一条覆盖路径上边的数量，我们最大化后者，就可以求得前者最小值。而在流网络二分图上，要求一个点不能同时与另外两个同向的边在一条覆盖路径上，所以本质上是求二分图最大匹配，最大流流量就是在同一条覆盖路径上边的数量。

所以答案是点数-最大流流量。