引论
对网络流算法的认识
网络流算法是一种高效实用的算法,相对于其它图论算法来说,模型更加复杂,编程复杂度也更高,但是它综合了图论中的其它一些算法(如最短路径),因而适用范围也更广,经常能够很好地解决一些搜索与动态规划无法解决的,看似 NP 的问题。
具体问题的应用
网络流在具体问题中的应用,最具挑战性的部分是模型的构造。这没有现成的模式可以套用,需要对各种网络流的性质了如指掌(比如点有容量、容量有上下限、多重边等等),并且归纳总结一些经验,发挥我们的创造性。
网络流有许多分支的问题,这里只为大家介绍最大流问题。涉及到 FF,EK,Dinic 三个算法。
注意:网络流部分的课程当中也有“增广路径”的概念,但这与匈牙利算法当中的增广路径含义不同。
- 二分图:通过拓展增广路径来获得更多的匹配
- 最大流:通过寻找增广路径来获取更大的流量
什么是网络流?
我们从一个简单的例子开始说起。
你所在的村庄新开通了地下流水管道,自来水厂源源不断的提供水,村民们用水直接或间接用水,而村庄用完的废水统一回收于另一点(设排来的水全部回收)。当然每个管道有一定的容量。求废水站最多可以汇聚多少水?
当然这是一个有向图。所有的水都从一个点流出(水厂),最后全部汇聚到一个点(废水站)。
网络流图
一个网络流图是一个没有自环的有向连通图,满足:
只有一个入度为 0 的点 S,称为 源
;
只有一个出度为 0 的点 T,称为 汇
;
每条边 e=(i,j) 有一个非负实数权值 ce,称为该边的容量
。
容许流
在网络流图中,对于每条边 e=(i,j) 给定实数 fe 为该边的流量
,如果满足
- 每条边的流量不大于容量(fe⩽)
- 每个点的入流量等于出流量(对于 x \neq S, T,\sum\limits_{e=(x, i)} f_e = \sum\limits_{e=(i, x)} f_e)
- 源点流出等于汇点流入 W = \sum\limits_{e=(S, i)} f_e = \sum\limits_{e=(i, T)} f_e
则这一组流量 f 称为该网络的一个容许流
,W 称为它的流量
。
最大流:求一个容许流使得它的 W 最大。
最大流算法
基本思路:
从流量为 0 的容许流开始,不断尝试寻找增流路径(增广路),增加容许流的流量,直到无法增加为止。
称为增广过程。
Ford-Fulkerson 标号算法
记录 v_e = c_e - f_e,为一条边的剩余容量。
定义残量网络:对于每条边 e=(u, v),其边权为 v_e,并对其增加一条反向边
e’=(v, u),边权为 f_e。
每次在残量网络中,任意
找一条从 S 到 T 的路径,边权均不为 0,则这条路径成为一条增广路
,这条路径上边权的最小值 w 为容许流流量的增量。
将这条路径上每一条边 e 的边权减去 w,并将其反向边 e’ 的边权加上 w。
若 e 为原图中的一条边,则相当于将该边的 f 增加了 w;否则相当于将 e’ 的 f 减少了 w(退流)。
正确性:
残量网络中每条边的边权不会变为负数,即保证了 0 \leqslant f_e \leqslant c_e;
每次增广时,一个点的入流量和出流量总是同时变化 w,总满足对于每个点的流量平衡;
每次增广时,S 的出流量和 T 的入流量会同时增加 w。
若存在最大流,则在最大流中每个点仍满足流量平衡,若要增加流量,则残量网络中必然存在满足要求的路径。
同时说明了只要最大流流量 W 有限,总在有限的时间内求出。
代码实现
struct edge {
int to, cap, rev;
};
vector<edge> g[MAX_V];
bool used[MAX_V];
// 向图中增加一条从 s 到 t 容量为 cap 的路径
void add_edge(int u, int v, int cap) {
g[u].emplace_back(v, cap, g[v].size());
g[v].emplace_back(u, 0, g[u].size()-1);
}
// 通过 dfs 寻找增广路
int dfs(int v, int t, int f) {
if (v == t) return f;
used[v] = true;
for (auto&& e : g[v]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
return 0;
}
// 求解从 s 到 t 的最大流
int max_flow(int s, int t) {
int flow = 0;
while (1) {
memset(used, 0, sizeof used);
int f = dfs(s, t, INF);
if (f == 0) return flow;
flow += f;
}
}
Edmonds-Karp 算法
{\rm FF} 算法的效率问题:其复杂度与边权相关。
注意到在图中 C 可能很大很大
比如说下面这张图
如果运气不好 这种图会让你的程序执行 200 次dfs
虽然实际上最少只要 2 次我们就能得到最大流
{\color{Blue} {Edmonds-Karp}} 算法:每次沿着一条最短(边数最少)的增广路进行增广。
在残量网络中寻找路径时使用 BFS
即可。
可以证明,{\rm EK} 算法的复杂度与边的容量无关,且增广路的条数不超过 \frac{m(n+2)}{2}。因此它的复杂度上界为 O(m^2n)(一般远达不到)。
Dinic 算法
考虑继续优化上述算法
在上述算法中,每一次我们只求出了一条增广路。
实际上,我们可以一次求出多条互不干扰的增广路进行增广。
每一次对残量网络进行分层:忽略边权为 0 的边,求出 S 到每个点 i 的最短距离 dist[i]。
考虑所有满足不为 0 且 dist[i] + 1 = dist[j] 的边 e=(i, j),这些边组成了一个 DAG
,DAG
上任意一条从 S 到 T 的路径均为最短路。
在该 DAG
上进行 {\rm DFS} 即可一次求出多条增广路。
当前弧优化
在 {\rm DFS} 的过程中,对于一条边 e = (i, j),如果已经不存在一条 j 到 T 的可用路径,则这条用已经不能再用于增广了。
对于每个点,记录它可能用于增广的第一条边。在 {\rm DFS} 的时候维护这个值,可以减少许多无用的搜索过程。
{\color{Green} {Dinic}} 算法的复杂度:
每次 {\rm DFS} 结束后最短路的长度一定增加,故分层与 {\rm DFS} 的次数为 O(n)
分层复杂度较低,瓶颈为 {\rm DFS} 的复杂度:
成功增广的部分,最多增广 m 次,每次最多 n 条边,复杂度 O(nm);
寻找增广路失败时后退的部分,由于当前弧优化,每次后退都会删除一条边,故复杂度 O(m)。
即总复杂度 O(n^2m)。
最大流最小割定理
定义 s-t 割
是节点集 V 的一个划分 (A, B),使得 s \in A 且 t \in B。
定义 (A, B) 割
的容量为 cap(A, B) = \sum\limits_{e \text{:从}A\text{中引出的边}} c(e)
最小割问题: 找到一个 s-t 割
满足它的容量最小
流值引理: 令 f 为任意流,(A, B) 为任意 s-t 割
。从 A 流出的量减去从 A 流入的量等于流 f 的流值,即 \sum\limits_{\text{流出} A \text{的边} e} f(e) - \sum\limits_{\text{流入} A \text{的边} e} f(e) = v(f)。
证明:
v(f) = \sum\limits_{\text{流出} \ s \ \text{的边} e} f(e)
根据流量守恒要求,A 中所有点除了 s 外,流入的量等于流出的量,因此 v(f) = \sum\limits_{v \in A} (\sum\limits_{\text{流出} \ v \ \text{的边} e} f(e) - \sum\limits_{\text{流入} \ v \ \text{的边} e} f(e))
若一条边的两端点都在 A 中,一定对应着一正一负的两项可以消掉,所以 v(f) = \sum\limits_{\text{流出} \ A \ \text{的边} e} f(e) - \sum\limits_{\text{流入} \ A \ \text{的边} e} f(e)
弱对偶性: 令 f 为任意的流,(A, B) 为任意的 s-t 割
,那么 f 的流值不超过割的容量。
证明:
\begin{aligned} v(f) &= \sum\limits_{\text{流出} \ A \ \text{的边} e} f(e) - \sum\limits_{\text{流入} \ A \ \text{的边} e} f(e) \\\ &\leqslant \sum\limits_{\text{流出} \ A \ \text{的边} e} f(e) \\\ &\leqslant \sum\limits_{\text{流出} \ A \ \text{的边} e} c(e) \\\ &= cap(A, B) \end{aligned}
最优性条件: 令 f 为任意的流,(A, B) 为任意的割。如果 v(f) = cap(A, B),那么 f 是最大流且 (A, B) 是最小割。
增广路定理: f 为最大流当且仅当没有增广路。
最大流最小割定理: 最大流的流值等于最小割的容量。
我们可以通过证明以下三个命题的等价性来证明以上两个定理。
(i) 存在一个割 (A, B) 使得 v(f) = cap(A, B)
(ii) f 是一个最大流
(iii) 对于 f,网络中不存在增广路
(i) \to (ii) 这是弱对偶引理的推论
(ii) \to (iii) 我们证明它的逆否命题。
令 f 是一个流。如果存在一条增广路,那么我们可以沿着这条增广路进行增广来提高流值,则 f 不是最大流。
(iii) \to (i) 令 f 为一个流,对应的残量网络中不存在增广路,A 为残量网络中由 s 可达的节点集合
由 A 的定义,s \in A。由 f 的定义,t \notin A。
\begin{aligned} v(f) &= \sum\limits_{\text{流出} \ A \ \text{的边} e} f(e) - \sum\limits_{\text{流入} \ A \ \text{的边} e} f(e) \\\ &= \sum\limits_{\text{流出} \ A \ \text{的边} e} c(e) \\\ &= cap(A, B) \end{aligned}
最小费用最大流(费用流)
根据增广路定理,我们只需要不断地走增广路就能找到最大流
所以我们每次找一条单位费用最小的增广路,然后进行增广,直到找不到
其中单位费用最小其实就是最短路问题