「知识总结」网络流【网络流】

简介

网络流是图论中一个博大精深的分支,主要包括最大流、最小割和费用流三个方面。本文主要介绍网络流的一些基础知识,少部分算法和证明的细节会被省略。

定义

一个网络 G=(V,E)G = (V, E) 是一张有向图,图中每条有向边 (x,y)E(x, y) \in E 都有一个给定的权值 c(x,y)c(x, y),称为边的容量。特别地,若 (x,y)E(x, y) \notin E,则 c(x,y)=0c(x, y) = 0。图中还有两个指定的特殊节点 SVS \in VTVT \in V (STS \neq T),分别称为源点汇点

f(x,y)f(x, y) 是定义在节点二元组 (xV,yV)(x \in V, y \in V) 上的实数函数,且满足:

  • f(x,y)c(x,y)f(x, y) \leqslant c(x, y)
  • f(x,y)=f(y,x)f(x, y) = -f(y, x)
  • xS,xT,(u,x)Ef(u,x)=(x,v)Ef(x,v)\forall x \neq S, x\neq T, \displaystyle \sum_{(u, x) \in E} f(u,x) = \sum_{(x, v) \in E} f(x, v)

ff 称为网络的函数。对于 (x,y)E(x, y) \in Ef(x,y)f(x, y) 称为边的流量c(x,y)f(x,y)c(x, y) - f(x, y) 称为边的剩余流量

网络流的性质:

  • 斜对称性质:按照流函数的定义,每条边的反向边其实都有一个负的流量
  • 流量守恒定律:网络中除源点、汇点以外任何节点不存储流,其流入总量等于流出总量。
  • 网络流模型可以形象地描述为:在不超过容量限制的前提下,流从源点不断产生,流经整个网络,最终全部归于汇点。

以下依次介绍:

  1. 最大流
  2. 最小割
  3. 费用流

1. 最大流

对于一个给定的网络,合法的流函数 ff 有很多。使得整个网络的流量 (S,v)Ef(S,v)\displaystyle \sum_{(S, v) \in E} f(S, v) 最大的流函数被称为网络的最大流,此刻的流量被称为网络的最大流量

计算最大流的算法有很多,这里简单涉及 Edmonds\text {Edmonds}-Karp\text {Karp} 算法和 Dinic\text {Dinic} 算法。

Edmonds-Karp 算法

若一条从源点 SS 到汇点 TT 的路径上各条边的剩余容量都大于 00,则称这条路径为一条增广路。显然,可以让一股流沿着增广路从 SS 流到 TT,使网络的流量增大。

Edmonds\text {Edmonds}-Karp\text {Karp} 算法的思想就是不断用 BFS\text {BFS} 寻找增广路,直至网络上不存在增广路为止。

在每轮寻找增广路的过程中,Edmonds\text {Edmonds}-Karp\text {Karp} 算法只考虑图中所以 f(x,y)<c(x,y)f(x, y) < c(x, y) 的边,用 BFS 找到任意一条从 SSTT 的路径,同时计算出路径上各边的剩余容量的最小值 minfminf,则网络的流量就可以增加 minfminf

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

在具体实现时,可以按照邻接表成对存储的技巧,把网络的每条有向边及其反向边存在邻接表下标相邻的两个位置,可以相互用 xor 1xor \ 1 得到。并且每条边只记录剩余容量 cfc - f 即可。当一条边 (x,y)(x, y) 流过大小为 ee 的流时,令 (x,y)(x, y) 的剩余流量减少 ee(y,x)(y, x) 的剩余流量增大 ee

Edmonds\text {Edmonds}-Karp\text {Karp} 算法的时间复杂度为 O(nm2)O(n \cdot m^2),在实际应用中则远远达不到这个上界,效率较高,一般能够处理 10310^310410^4 规模的网络。

Dinic 算法

在任意时刻,网络中所有节点以及剩余容量大于 00 的边构成的子图被称为残量网络Edmonds\text {Edmonds}-Karp\text {Karp} 算法每轮可能会遍历整个残量网络,但只找出 11 条增广路,还有进一步优化的空间。

定义节点的层次 d(x)d(x) 表示 SSxx 最少需要经过的边数。在残量网络中,满足 d(x)=d(y)+1d(x) = d(y) + 1 的边 (x,y)(x,y) 构成的子图被称为分层图。分层图显然是一张有向无环图。

Dinic\text {Dinic} 算法不断重复以下步骤,直到在残量网络中 SS 不能到达 TT

  1. 在残量网络上 BFS\text {BFS} 求出节点的层次,构造分层图。
  2. 在分层图上 DFS\text {DFS} 寻找增广路,在回溯时实时更新剩余容量,同时去掉增广完毕的点 (剪枝)。

Dinic\text {Dinic} 算法的时间复杂度为 O(n2m)O(n^2 \cdot m),在实际应用中则远远达不到这个上界,可以说是比较容易实现的效率最高的网络流算法之一,一般能处理 10410^410510^5 规模的网络。特别地,Dinic\text {Dinic} 算法求解二分图匹配的时间复杂度为 O(mn)O(m \cdot \sqrt n),实际表现则更快。

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
// Luogu-3376 网络最大流
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100010;
struct edge {
int to, cap, nxt;
} e[maxn * 2];
int n, m, cnt, head[maxn], level[maxn];

int id(int x, int y) {
return (x - 1) * m + y;
}

void add_edge(int from, int to, int cap) {
e[cnt] = (edge){to, cap, head[from]}, head[from] = cnt++;
e[cnt] = (edge){from, 0, head[to]}, head[to] = cnt++;
}

int bfs(int s, int t) {
memset(level, 0, sizeof(level));
queue<int> q;
level[s] = 1;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = head[v]; i != -1; i = e[i].nxt) {
if (e[i].cap > 0 && !level[e[i].to]) {
level[e[i].to] = level[v] + 1;
q.push(e[i].to);
}
}
}
return level[t];
}

int dfs(int v, int t, int f) {
if (v == t) {
return f;
}
int add = 0;
for (int i = head[v]; i != -1 && add < f; i = e[i].nxt) {
if (e[i].cap > 0 && level[v] + 1 == level[e[i].to]) {
int d = dfs(e[i].to, t, min(e[i].cap, f - add));
if (d > 0) {
e[i].cap -= d;
e[i ^ 1].cap += d;
add += d;
} else {
level[e[i].to] = -1;
}
}
}
return add;
}

int dinic(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
flow += dfs(s, t, 0x3f3f3f3f);
}
return flow;
}

int main() {
memset(head, -1, sizeof(head));
int s, t;
cin >> n >> m >> s >> t;
while (m--) {
int from, to, cap;
cin >> from >> to >> cap;
add_edge(from, to, cap);
}
cout << dinic(s, t) << endl;
return 0;
}

2. 最小割

给定一个网络 G=(V,E)G = (V, E),源点为 SS,汇点为 TT。若一个边集 EEE' \subseteq E 被删去之后,源点 SS 和汇点 TT 不再连通,则称该边集为网络的。边的容量之和最小的割称为网络的最小割

最大流最小割定理

任何一个网络的最大流量等于最小割中边的容量之和,简记为:最大流 == 最小割

假设最小割 << 最大流,那么割去这些边之后,因为网络流量尚未最大化,所以仍然可以找到一条 SSTT 的增广路,与 S,TS, T 不连通矛盾,故最小割 \geqslant 最大流。如果能给出一个最小割 == 最大流的构造方案,即可得到上述定理。

求出最大流后,从源点开始沿残量网络 BFS\text {BFS},标记能够到达的点。EE 中所有连接已标记点 xx 和未标记点 yy 的边 (x,y)(x, y) 构成该网络的最小割。详细证明略。

3. 费用流

给定一个网络 G=(V,E)G = (V, E),每条边 (x,y)(x, y) 除了有容量限制 c(x,y)c(x, y),还有一个给定的单位费用 w(x,y)w(x, y)。当边 (x,y)(x, y) 的流量为 f(x,y)f(x, y) 时,就要花费 f(x,y)w(x,y)f(x, y) \cdot w(x, y) 的费用。该网络中总花费最小的最大流被称为最小费用最大流,花费最大的最大流被称为最大费用最大流,二者合称为费用流模型。需要注意费用流的前提是最大流,然后再考虑费用的最值。

计算费用流一般使用 Edmonds\text {Edmonds}-Karp\text {Karp} 算法或 Zkw\text {Zkw} 费用流,这里仅介绍 Edmonds\text {Edmonds}-Karp\text {Karp} 算法。

Edmonds-Karp 算法

Edmonds\text {Edmonds}-Karp\text {Karp} 求解最大流的基础上,把用 BFS\text {BFS} 寻找一条增广路改为用 SPFA\text {SPFA} 寻找一条单位费用之和最小的增广路 (也就是把 w(x,y)w(x, y) 当做边权,在残量网络上求最短路) 即可求出最小费用最大流。注意:一条反向边 (y,x)(y, x) 的费用应设为 w(x,y)-w(x, y)

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
// Luogu-3381 最小费用最大流
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010, maxm = 50010;
int n, m, cnt, max_flow, ans;
int head[maxn], dist[maxn], pre[maxn], incf[maxn], inq[maxn];
struct edge {
int to, cap, cost, nxt;
} e[maxm << 1];

void add_edge(int from, int to, int cap, int cost) {
e[cnt] = (edge){to, cap, cost, head[from]}, head[from] = cnt++;
e[cnt] = (edge){from, 0, -cost, head[to]}, head[to] = cnt++;
}

bool spfa(int s, int t) {
fill(dist + 1, dist + n + 1, INT_MAX);
memset(inq, 0, sizeof(inq));
queue<int> q;
q.push(s);
dist[s] = 0;
inq[s] = 1;
incf[s] = 0x3f3f3f3f;
while (!q.empty()) {
int v = q.front();
inq[v] = 0;
q.pop();
for (int i = head[v]; i != -1; i = e[i].nxt) {
if (e[i].cap > 0 && dist[e[i].to] > dist[v] + e[i].cost) {
dist[e[i].to] = dist[v] + e[i].cost;
incf[e[i].to] = min(incf[v], e[i].cap);
pre[e[i].to] = i;
if (!inq[e[i].to]) {
q.push(e[i].to);
inq[e[i].to] = 1;
}
}
}
}
return dist[t] != INT_MAX;
}

void update(int s, int t) {
int x = t;
while (x != s) {
int i = pre[x];
e[i].cap -= incf[t];
e[i ^ 1].cap += incf[t];
x = e[i ^ 1].to;
}
max_flow += incf[t];
ans += dist[t] * incf[t];
}

void edmonds_karp(int s, int t) {
while (spfa(s, t)) {
update(s, t);
}
}

int main() {
memset(head, -1, sizeof(head));
int s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);
while (m--) {
int u, v, w, f;
scanf("%d %d %d %d", &u, &v, &w, &f);
add_edge(u, v, w, f);
}
edmonds_karp(s, t);
printf("%d %d\n", max_flow, ans);
return 0;
}