网络流
概述
网络(network)是指一个特殊的有向图 \(G=(V,E)\) ,其与一般有向图的不同之处在于有容量和源汇点。
-
\(E\) 中的每条边 \((u, v)\) 都有一个被称为容量(capacity)的权值,记作 \(c(u, v)\)。当 \((u,v)\notin E\) 时,可以假定 \(c(u,v)=0\)。
-
\(V\) 中有两个特殊的点:源点(source)\(s\) 和汇点(sink)\(t\)(\(s \ne t\))。
一条简单增广路上存在一个流量 \(flow\) 指当前增广路上通过的流量,在最大流问题中,这个值则是增广路上所有容量的权值最小值。
- 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 \(0 \leq f(u,v) \leq c(u,v)\)。
- 流守恒性:除源汇点外,任意结点 \(u\) 的净流量为 \(0\)。其中,我们定义 \(u\) 的净流量为 \(f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)\)。
最大流
最大流是指在图 \(G\) 上选择合适的流量 \(f\) ,使得整个网络的流量。
通常大家应该能想到 dfs
去寻找每一条增广路,统计这条增广路的最大流量 \(maxflow\),将这条增广路上所有容量减去 \(maxflow\),表示这条路已经流过了,减去已经流过的流量。
但有时会出现特殊情况:如下图,在 dfs
中,我们会先走 \(u\rightarrow v\) 的路径,这样会使最大流只有1,但实际应该为 \(u\rightarrow q\) 和 \(p\rightarrow v\) 两条流。
所以怎么处理呢,我们发现 \(u\rightarrow v\) 的路径其实只更改了\(u\rightarrow v\) 的容量大小,所以不妨在原图上全建反边,边权容量初始为 \(0\),若有流量经过,在原图\(-=flow\) 时,反图应\(+=flow\)。
这样就可以使最大流不出错。
\(FF(Ford-Fulkerson)增广算法\)
最基础的网络流最大流算法,也是大家最能理解的,通过 dfs
遍历增广路求最大流量,再将这条增广路上的容量减去最大容量,反边加上最大容量,反复操作直至求出答案,复杂度为 \(O(fM)\),\(f\) 为网格的最大流。在此不再详述
\(EK(Edmonds-Karp)算法\)
就是 \(FF\) 的变形,基本思路仍不变,不过是把 dfs
变为时间更少的 bfs
算法,bfs
的优点是层次遍历,不会出现环,节省时间,实现方法与 FF
类同,复杂度为 \(O(NM^2)\)。
\(Dinic算法\)
通过使用 bfs
时进行分层,每层再使用 dfs
去寻找这个层次图 \(G_L\) 的最大增广流 \(f_b\),\(f_b\) 称为 \(G_L\) 的阻塞流。
流程如下:
- 在 \(G_f\) 上
BFS
出层次图 \(G_L\)。 - 在 \(G_L\) 上
DFS
出阻塞流 \(f_b\)。 - 将 \(f_b\)并到原先的流 \(f\) 中,即 \(f \leftarrow f + f_b\)。
- 重复以上过程直到不存在从 \(s\) 到 \(t\) 的路径。
此时的 \(f\) 即为最大流。
当前弧优化
如果某一时刻我们已经知道了边 \((u,v)\) 已经增广到极限,即边 \((u,v)\) 已无剩余容量或 \(v\) 的后侧已增广至阻塞,则 \(v\) 的流量没有必要再尝试流向出边 \((u,v)\) 。据此,我们对于每个节点 \(u\),我们维护 \(u\) 的出边表中第一条边为还有必要尝试的出边,我们称这个维护指针为当前弧。
通过这种优化,Dinic
算法时间复杂度为 \(O(N^2M)\) 。