Skip to content

最大流学习笔记

笔记约 2.5 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

最大流问题是求解图上从源点流向汇点的最大流量的问题。

求解最大流问题主要有两种算法:Edmonds-Karp 动能算法(EK 算法)和 Dinic 算法,其中后者在算法竞赛中更为常用。

#基本概念

#流网络

流网络 G=(V,E)G = (V, E)(Flow Network) 是一个有向图,图中每条边 (u,v)E(u, v) \in E 有一个非负的 容量值 c(u,v)0c (u, v) \geq 0。而且,如果边集合 EE 包含一条边 (u,v)(u, v),则图中不存在反方向的边 (v,u)(v, u)。为了方便起见,如果 (u,v)E(u, v) \notin E,则定义 c(u,v)=0c(u, v) = 0

在流网络的所有节点中,有两个特殊的点:源点 ss 和汇点 tt (st)(s \ne t)

#

f(u,v)f(u, v) 定义在二元组 (uV,vV)(u \in V, v \in V) 上的实数函数且满足

  1. 容量限制(Capacity Constraints):对于每条边,流经该边的流量不得超过该边的容量,即 u,vV,f(u,v)c(u,v)\forall u, v \in V, f(u, v) \leq c(u, v)
  2. 流量守恒(Flow Conservation):从源点流出的流量等于汇点流入的流量,即 xV{s,t},(u,x)Ef(u,x)=(x,v)Ef(x,v)\forall x \in V - \{s, t\}, \sum_{(u, x) \in E} f(u, x) = \sum_{(x, v) \in E} f(x, v)

那么 ff 称为网络 GG 的流函数。

对于 (u,v)E(u, v) \in Ef(u,v)f(u, v) 称为边的 流量c(u,v)f(u,v)c(u, v) - f(u, v) 称为边的 剩余容量(Residual Capacity),可以记作 cf(u,v)c_f(u, v)。整个网络的流量为 (s,v)Ef(s,v)\sum_{(s, v) \in E} f(s, v),即从源点发出的所有流量之和。为了方便起见,如果 (u,v)E(u, v) \notin E,则定义 f(u,v)=0f(u, v) = 0

一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述两个性质。

流函数的完整定义如下:

f(u,v)={f(u,v),(u,v)Ef(v,u),(v,u)E0,(u,v)E,(v,u)Ef(u, v) = \left\{ \begin{aligned} & f(u, v), & (u, v) \in E \\ & -f(v, u), & (v, u) \in E \\ & 0, & (u, v) \notin E, (v, u) \notin E \\ \end{aligned} \right.

#残量网络

对于流函数 ff,残量网络 GfG_f(Residual Network)是网络 GG 中所有节点和剩余容量大于 00 的边构成的子图,即

Gf=(Vf=V,Ef={(u,v)E,cf(u,v)>0})G_f = (V_f = V, E_f = \left \{(u, v) \in E , c_f(u, v) > 0 \right\})

注意,剩余容量大于 00 的边可能不在原图 GG 中(根据容量、剩余容量的定义以及流函数的斜对称性得到)。可以理解为,残量网络中包括了那些还剩了流量空间的边构成的图,也包括虚边(即反向边)。

#增广路

在原图 GG 中若存在一条从源点到汇点的路径上所有边的剩余容量都大于 00,则这条路径被称为增广路(Augmenting Path)。

#Edmonds-Karp 算法

Edmonds-Karp 算法的基本思路很简单:不断地使用 BFS 去寻找增广路,直到网络上不存在增广路为止。

在每轮寻找增广路的过程中,Edmonds-Karp 算法只考虑所有 cf(u,v)0c_f(u, v) \geq 0 的边,用 BFS 找到任意一条从 sstt 的路径,同时计算出路径上各边的剩余容量的最小值 minf\mathit{minf},则网络的流量就可以增加 minf\mathit{minf}

需要注意的是,当一条边的流量 f(u,v)>0f(u, v) > 0 时,根据斜对称性质,它的反向边流量 f(v,u)<0f(v, u) < 0,此时必定有 f(v,u)<c(v,u)f(v, u) < c(v, u)。故 Edmonds-Karp 算法在 BFS 时除了原图的边集 EE 外,还应该考虑遍历 EE 中每条边的反向边。

在实现时,只需要维护残量网络即可。当一条边 (u,v)(u, v) 流过大小为 ee 的流时,令 (u,v)(u, v) 的剩余容量减小 (e)(e)(v,u)(v, u) 的剩余流量增大 ee 即可。

Edmonds-Karp 算法的时间复杂度为 O(VE2)O(VE^2)。然而在实际运用中远远达不到这个上界,效率较高,可以处理 10310410^3 \sim 10^4 规模的网络。

来自 GitHub Copilot 的补全(未验证):然而在实际应用中,这个算法的时间复杂度可以降低到 O(VE)O(VE),因为在每轮 BFS 时,只需要更新 EE 中的边的剩余容量,而不需要更新 VV 中的节点。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstring>
#include <iostream>
#include <limits>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1005,
M = 10005;

int n, m, s, t, ans;

// Graph
int idx, head[N], ver[M << 1], edge[M << 1], next[M << 1];

void add(int u, int v, int w) {
next[idx] = head[u];
ver[idx] = v;
edge[idx] = w;
head[u] = idx++;
}

// Edmonds-Karp
int d[N], pre[N];
bool vis[N];

bool bfs() {
memset(vis, 0x00, sizeof(vis));
std::queue<int> q;
q.push(s);
vis[s] = true;
d[s] = std::numeric_limits<int>::max();
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; ~i; i = next[i]) {
if (edge[i]) {
int y = ver[i];
if (vis[y]) continue;
d[y] = std::min(d[x], edge[i]);
pre[y] = i; // 记录前驱
q.push(y);
vis[y] = true;
if (y == t) return true;
}
}
}
return false;
}

void update() { // 更新增广路及其反向边的剩余容量
int x = t;
while (x != s) {
int i = pre[x];
edge[i] -= d[t];
edge[i ^ 1] += d[t];
x = ver[i ^ 1];
}
ans += d[t];
}

int main() {
std::ios::sync_with_stdio(false);
memset(head, 0xff, sizeof(head));
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
while (bfs()) update();
cout << ans << endl;
return 0;
}

#Dinic 算法

Edmonds-Karp 算法每轮可能会遍历整个残量网络,但只找出一条增广路,还有进一步优化的空间。

Dinic 算法不断重复以下步骤,直到在残量网络中 ss 不能到达 tt

  1. 在残量网络上 BFS 求出节点的层次,构造分层图。
  2. 在分层图上 DFS 求出增广路,在回溯时实时更新剩余容量。另外,每个点可以流向多条出边,同时还加入了若干剪枝(参考程序注释)。

Dinic 算法的时间复杂度为 O(V2E)O(V^2E)。但在实际中远远达不到这个上界,一般能够处理 10410510^4 \sim 10^5 规模的网络,特别地,在求解稠密图上的最大流问题是效率要比前文提到的 Edmonds-Karp 算法更高。


Dinic 算法中的两个优化:

  1. 多路增广:每找到一条增广路时,若还有残余流量存在,那么可以再找出其他的增广路来利用这些残余流量。这样就可以在一次 DFS 中找出多条增广路,大大提高了算法的效率。
  2. 当前弧优化:如果一条边已经被增广过,那么该边就没有可能被增广第二次。那么,当下一次进行增广的时候,就可以不必再走那些已经被增广过的边。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstring>
#include <iostream>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 205,
M = 5005;

int n, m, s, t, flow;
long long ans;

// Graph
int idx, head[N], edge[M << 1], ver[M << 1], next[M << 1];

void add(int u, int v, int w) {
next[idx] = head[u];
edge[idx] = w;
ver[idx] = v;
head[u] = idx++;
}

// Dinic
int d[N], cur[N];

bool bfs() {
memset(d, 0x00, sizeof(d));
std::queue<int> q;
d[s] = 1;
q.push(s);
cur[s] = head[s];

while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = next[i]) {
int v = ver[i],
w = edge[i];
if (w && !d[v]) {
d[v] = d[u] + 1;
cur[v] = head[v];
if (v == t) return true;
q.push(v);
}
}
}
return false;
}

int dinic(int u, int limit) {
if (u == t) return limit;

int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = next[i]) {
cur[u] = i; // 当前弧优化

int v = ver[i],
w = edge[i];
if (w && d[v] == d[u] + 1) {
int k = dinic(v, std::min(edge[i], limit - flow));
if (!k) d[v] = 0; // 剪枝:去掉增广完毕的点
edge[i] -= k;
edge[i ^ 1] += k;
flow += k;
}
}
return flow;
}

int main() {
std::ios::sync_with_stdio(false);
memset(head, 0xff, sizeof(head));
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
while (bfs()) {
while (flow = dinic(s, 0x3f3f3f3f)) ans += flow;
}
cout << ans << endl;
return 0;
}

#参考资料

  1. 0x6A 网络流初步,《算法竞赛进阶指南》(ISBN 978-7-83009-313-6,河南电子音像出版社),李煜东,2019 年 5 月第 5 次修订版。
  2. 第 26 章 最大流,《算法导论》中译本(ISBN 978-7-111-40701-0,机械工业出版社),2013 年 1 月第三版。
  3. 1.1.1 网络流的基本概念,AcWing 算法进阶课,闫学灿,2020 年 7 月 25 日。
  4. 1.1.2 最大流,AcWing 算法进阶课,闫学灿,2020 年 7 月 31 日 ~ 2020 年 8 月 8 日。
  5. 网络流简介,图论,OI Wiki,2021 年 7 月 11 日。