网络流从入门到入土 - By Shq

网络流是个十分常用的方法,拥有很多用途

之前的讲解太草率了qwq,这一篇我们来好好介绍一下网络流

网络流 - 网络

网络是一张有向图,有且仅有 一个汇点和一个源点

我们来举一个 简单易懂 的栗子:

你是一个工厂老板

你有一座超大的工厂,大到它可以制造任意多的货物。但是众所周知,工厂是不会建在市区的。

从工厂到销售处之间有若干车站,车站间有若干车次。每个车次有一个起点、一个终点(单向的),还有一个容量,指你最多可以利用个车次载多少货物。最大化你从工厂运到销售处的货物量

这是一个很显然的栗子

栗子中你的工厂就是源点,销售处(我们规定只有一个销售处)就是汇点

画一个简单的图:

网络流

By Shq + GeoGebra

图中的 SS 代表源点,TT 代表汇点

每条边表明了流量

我们将⼀个合法解称作⼀个流,⼀条边被经过的次数称作其流量;

最终运输的货物总数称作整个流的流量


容量限制:每条边被经过的次数不得超过它的容量 \to 每条边的流量不超过其流量

流量平衡:流由若⼲从源点到汇点的路径组成 \to 除源点和汇点外,对于每个点,流⼊它的流量和等于从它流出的流量和

最⼤化货物量 \to 最⼤化整个流的流量 \to 最⼤化从源点流出的流量

网络的一些性质

网络流的性质有很多,这里先介绍一些常用的性质

  • 容量:capacity(e)\mathrm{capacity}(e) 表示一条有向边 e(u,v)e(u, v) 的最大允许的流量
  • 流量:flow(e)\mathrm{flow}(e) 表示一条有向边 e(u,v)e(u, v) 总容量中已被占用的流量
  • 剩余容量:即 capacity(e)flow(e)\mathrm{capacity}(e) - \mathrm{flow}(e),表示当前时刻某条有向边 e(u,v)\mathrm{e}(u, v) 总流量中未被占用的部分
  • 反向边:原图中每一条有向边在残量网络中都有对应的反向边,反向边的容量为 \infty,容量的变化与原边相反;『反向边』的概念是相对的,即一条边的反向边的反向边是它本身
  • 残量网络:在原图的基础之上,添加每条边对应的反向边,并储存每条边的当前流量。残量网络会在算法进行的过程中被修改
  • 增广路(augmenting path\mathrm{augmenting\ path}):残量网络中从源点到汇点的一条路径,增广路上所有边中最小的剩余容量为增广流量
  • 增广(augmenting\mathrm{augmenting}):在残量网络中寻找一条增广路,并将增广路上所有边的流量加上增广流量的过程
  • 层次:level(u)\mathrm{level}(u) 表示节点 uu 在层次图中与源点的距离
  • 层次图:在原残量网络中按照每个节点的层次来分层,只保留相邻两层的节点的图,满载(即流量等于容量)的边不存在于层次图中

这里当然有一些 dinic 的内容,这里看看就好啦

最大流

现在我们想一种状况

你工厂生产的产品十分畅销,销售部经常卖光,你每次都要制造产品,再运过去很麻烦。于是,你制造了 109+710^9+7 顿货物,但是由于每条边都有一个流量限制,到达销售部的货物肯定不会是你发出货物的数量

你开始思考,我们最多生产多少顿货物,可以让销售部收到同样多的货物

这个货物的数量就是这个网络的最大流


我们先看一种 看似正确的 解法

Shq 蒟蒻解法:

找⼀条任意的路径并流过去,直到找不到一条合法的路径qwq

我们来考虑一下反例:

反例

我们要求这个网络的最大流

肉眼都能看出这个网络的最大流是 22

我们沿用刚刚的思路,假如我们看到了这样一条路径:

反例2

这个算法会有一个错误的答案 11


我们想想如何改进这个算法,首先我们看一看我们失败的原因

我们失败的原因是我们选择了一条错误的路径

那个.....有什么办法可以 反悔 呢?

如何做到 可以反悔

每次我们找到了道路后,我们可以建一条 反向边 ,容量为这条边的容量

减少⼀条边上 kk 的流量,相当于反向流过来 kk 的流量

这个还是⽐较显然的。假设你把⼀些货物从 xx 地运到 yy 地,后来你发现 运错了,那就再运回来就⾏了qwq

定义: ⼀条边的残量,是指它还能流多少流量(即容量减去当前流量)

反向边

这样,我们就又能发现一条道路!

新的道路

现在这个网络的最大流就显然是 22

这条路径就叫做增广路 (augmenting path\mathrm{augmenting\ path}),当然,增广路不止这一条qwq

最大流 - EK\text{EK} 算法

我们来给这个简单显然的方法整理一下:

Ford-Fulkerson-Method(G,S,T)\text {Ford-Fulkerson-Method}(G,S,T)

  1. initialize flowf to 0\text{initialize flow}f \text{ to } 0
  2. have an augmenting path \text{have an augmenting path }pp in\text{in} GfG_f
  3.     augment flow f along p\ \ \ \ \text{augment flow }f \text{ along } p
  4. return f\text{return }f

这明显就是贪心啊qwq


我们来尝试证明一下:

首先,对于 Ford-Fulkerson\text {Ford-Fulkerson} 算法求出的流为 ff ,ff 对应的残余网络中从 SS 可达的顶点集合为 ss ,因为 ff 对应的残余网络中不存在从 STS\to T的路径了

那么显然,在残余网络中,任意一条从 § 中的边流量 f=cf=c ,任意一条从反向弧 f=0f=0 ,这个一定是满足,如果不满足,那么 ss 集合还可以扩充顶点,与前提矛盾。因此,§ 的割的容量等于流的大小。则可以证明裸的増广路 ford\text{ford} 算法是正确的

最小割

我们刚刚在证明的时候出现了一个十分神奇的 字,那么他到底是啥呢?

所谓图的割,指的是某个顶点集合 ss 属于 vv ,从 ss 出发的所有边的集合成为割 § ,这些边的容量和被称为割的容量,如果有源点 SS 属于 ss ,汇点 TT 属于 § ,则称之为 STS-T 割,如果将 STS-T 割的所有边都在原图中去掉,则不再有 STS\to T的路径

我们还是举个栗子:

又双叒叕是这个图:

img

你和某家工厂的老板有仇

你想破坏他的工厂销售,但是明显的,你破坏工厂和销售部明显是不明智的,你可以破坏他工厂的运输即可qwq

你需要找到一些 道路,使从工厂到销售部没有道路链接,但是你并非想花费很大力气,你想找到一些花费力气最小的道路,选出⼀些边的集合,使得删除它们之后从源点⽆法到达汇点,那么这个集合就叫做⼀个

这些边的容量之和称作这个割的容量


我们任取一个割,我们发现它始终好像比最大流大的流量?

从源点到汇点的每条路径都会经过割上的⾄少⼀条边。割掉这些边之后,把源点能到达的点放到左边,不能到达的放到右边。显然源点到汇点的流量不会超过从左边⾛向右边的次数,⽽这⼜不会超过从左边到右边的边的容量之和。

直观⼀点,假设你是在⻋装着货物的时候炸掉了它。

每个货物你⾄少付出 11 的代价炸掉(流量⼩于容量的时候你要付出⽐货物 数更多的代价),所以你炸的代价 不会⼩于 货物数

对于一个网络

网络

我们可以直观的看出来从 SS \to TT 的最大流是 88

它的最小割为

网络的最小割

经过我们的实验发现,最小割的容量等于最大流的流量

这个和最小割最大流有关,我们就干脆命名为 最小割最大流定理

这意味着⼀个惊⼈的事实:你能够仅付出和货物数相同的代价,就把你的仇⼈的财路炸断!

这自然是看起来很玄学的,我们想想为什么这个是成立的

最小割最大流定理

求证:最小割的容量等于最大流的流量,并且 FF\text{FF} 能够正确地求出来它


考虑 FF\text{FF} 算法结束时,残量⽹络上没有了增⼴路。那么我们假设这时候,从源点经过残量⽹络能到达的点组成的集合为 XX ,不能到达的点为 YY 。显然汇点在 YY ⾥,并且残量⽹络上没有从 XXYY 的边。

可以发现以下事实成⽴:

  1. YYXX 的边流量为 00 。如果流量不为 00 那么应该存在⼀条从 XXYY 的反向边,于是⽭盾。
  2. XXYY 的边流量等于其容量。只有这样它才不会在残量⽹络中出现。

根据第⼀个条件,我们可以得知:没有流量从 XXYY 之后⼜回到了 XX 。所以当前流量应该等于从 XXYY 的边的流量之和,⽽根据第⼆个条件它⼜等于从 XXYY 的边容量之和.⽽所有从 XXYY 的边⼜构成⼀个割,其容量等于这些边的容量之和

这意味着我们找到⼀个流和⼀个割,使得前者的流量等于后者的容量。⽽根据前⾯的结论,最⼤流的流量不会超过这个割的容量,所以这个流⼀定是最⼤流!

同样的,最⼩割的容量也不会⼩于这个流的流量,所以这个割也⼀定是最⼩割。

⽽这就是 FF\text{FF} ⽅法最后的局⾯(由于 FF\text{FF} 会终⽌,所以它必定求出这样⼀个局⾯),由此我们得出结论:

FF是正确的,并且最大流等于最小割。 (⽽最⼩割最⼤流定理还可以通过线性规划对偶定理证明)不⽤管这个⻤玩意。

证毕撒花.

其他最大流算法

窝就扔一个最大流板子的链接:[POJ]最大流板子


我们发现 EK\text{EK} 算法的复杂度 O(nm2)O(nm^2) 太⾼(虽然⽹络流⼏乎没有跑到上界的情况,但复杂度还是在⼀定程度上代表了算法效率)

有⼀个显然的优化:

如果增⼴⼀次之后发现最短路没有变化,那么可以继续增⼴;直到从源点到汇点的增⼴路增⼤,才需要再跑⼀遍 bfsbfs

bfsbfs 之后,我们取出那些可能在最短路上的边,即 dis[to] = dis[from] + 1\text{dis[to] = dis[from] + 1} 的那些边。显然这些边构成的图中没有环。我们只需要沿着这种边尽可能的增⼴即可。

我们利⽤ dfsdfs 增广。

有⼀个函数 int dfs(int x, int T, int maxflow) 表示从 xx 出发寻找到汇点 TT 的增广路,寻找到 maxflow\text{maxflow} 个流量为止,并相应的增广。其返回值为实际增广了多少(因为有可能找不到 maxflow\text{maxflow} 条增广路)


Dinic\text{Dinic} 复杂度可以证明为 O(n2m)O(n^2 m) 。在某些特殊情况下(每个点要么仅有⼀条⼊边且容量为 11,要么仅有⼀条出边且容量为 11 )其复杂度甚至能做到 O(mn)O(m\sqrt n)

Dinic 算法

Dinic\text{Dinic} 算法的过程:

  1. 遍历残量网络,建立层次图;
  2. 在层次图上寻找任意一条增广路,进行增广,并将答案加上增广流量;
  3. 重复第 22 步,直至层次图中不存在增广路,回到第 11 步重新建立层次图;
  4. 直到层次图无法建立,则当前流量即为最大流量。

每次建立层次图后都可以进行多次增广,无法增广时重新建立层次图,此时的层次图不再包含之前进行增广后满载的边。无法建立层次图时,说明源点到汇点的任意一条简单路径中,都至少有一条边满载,这也在直观上验证了最小割最大流定理

Dinic(G,S,T)\text{Dinic}(G,S,T)

  1. make Layered graph in G\text{make Layered graph in }G
  2. do\text{do}
  3.     augment flow f along p\ \ \ \ \text{augment flow }f \text{ along } p
  4. until there do not any augmenting flow in G\text{until there do not any augmenting flow in } G
  5. goto 1 remake Layered graph until cannot make Layered graph\text{goto 1 remake Layered graph until cannot make Layered graph}

dinic\text{dinic} 伪代码

(假设 TT 是⼀个全局变量,表示汇点)邻接表存储,head[x] 表示从 xx 出发 的第⼀条边,next[i] 表示 ii 的下⼀条边。最后⼀条边的 next1-1

1
2
3
4
5
6
7
8
9
10
11
12
int dfs(int x, int T, int maxflow) {
if (x == T) return maxflow;
int ans = 0;
for (int i = head[x];i != -1 && ans < maxflow; i = next[i]) {
if (dis[to[i]] != dis[x] + 1 || ret[i] == 0) continue;
int f = dfs(to[i], T, min(maxflow - ans, ret[i]))
ret[i] -= f;
ret[rev[i]] += f;
ans += f;
}
return ans;
}

Dinic\text{Dinic} 的主过程如下:

1
2
3
4
5
int Dinic(int S, int T) {
int ans = 0;
while (bfs(S, T)) ans += dfs(S, T, 0x7fffffff);
return ans;
}

这段代码⼗分简洁qwq


DinicDinic 有一个常见的优化 — 当前弧优化

该优化基于一个显而易见的事实,每次建立层次图后,如果在某一次增广前,某个点有一条边增广过了,则这条边在当前的层次图中不会再用到了,即下一次 DFSDFS 这个点的时候直接可以从这条边的下一条边开始


SAP 算法

距离标号:

所谓距离标号 ,就是某个点到汇点的最少的弧的数量(即边权值为1时某个点到汇点的最短路径长度)

设点 ii 的标号为 levelilevel_i,那么如果将满足 leveli=levelj+1level_i=level_j+1 的弧 (i,j)(i,j) 叫做允许弧 ,且增广时只走允许弧

断层(本算法的 GapGap 优化思想)

gapigap_i 数组表示距离标号为 ii 的点有多少个,如果到某一点没有符合距离标号的允许弧,我那么需要修改距离标号来找到增广路

如果重标号使得 gapgap 数组中原标号数目变为 00 ,则算法结束

我们学过毒瘤的EKEK算法,我们想想优化-如果能让每次寻找增广路时的时间复杂度降下来,那么就能提高算法效率了,使用 距离标号的最短增广路算法 就是这样的

SAP(G,S,T)\text{SAP}(G,S,T)

  1. initialize level, gap \text{initialize} \text{ level, gap }
  2. find e(u,v) with leveli=levelj+1\text{find }e(u,v)\text{ with level}_i=\text{level}_j+1
  3. find augmenting path along e(u,v)\text {find augmenting path along e}(u,v)

SAPSAP Code:

1
/*qwq窝才不会给你代码*/

ISAP算法

原图存在两种子图,一个是残量网络,一个是允许弧组成的图

残量网络保证可增广,允许弧保证最短路(时间界较优)

所以,在寻找增广路的过程中,一直是在残量网络中沿着允许弧寻找。因此,允许弧应该是属于残量网络的,而非原图的

换句话说,我们沿着允许弧,走的是残量网络(而非原图)中的最短路径

当我们找到沿着残量网络找到一条增广路,增广后,残量网络肯定会变化(至少少了一条边),因此决定允许弧的 dd 数组要进行相应的更新(顺便提一句,DinicDinic 的做法就是每次增广都重新计算 dd 数组)

然而,ISAP 「改进」的地方之一就是,其实没有必要马上更新 dd 数组。这是因为,去掉一条边只可能令路径变得更长,而如果增广之前的残量网络存在另一条最短路,并且在增广后的残量网络中仍存在,那么这条路径毫无疑问是最短的。所以,ISAP 的做法是继续增广,直到遇到死路,才执行 retreat\text{retreat} 操作

说到这里,大家应该都猜到了,retreat\text{retreat} 操作的主要任务就是更新 dd 数组。那么怎么更新呢?

非常简单:假设是从节点 uu 找遍了邻接边也没找到允许弧的;再设一变量 mm,令 mm 等于残量网络中 uu 的所有邻接点的 dd 数组的最小值,然后令 d[u]d[u] 等于 m+1m+1 即可。这是因为,进入 retreat\text{retreat} 环节说明残量网络中 uutt 已经不能通过(已过时)的允许弧相连

那么 uutt 实际上在残量网络中的最短路的长是多少呢?(这正是 dd 的定义!)

显然是残量网络中 uu 的所有邻接点和 tt 的距离加 11 的最小情况。特殊情况是,残量网络中 uu 根本没有邻接点。

如果是这样,只需要把 d[u]d[u] 设为一个比较大的数即可,这会导致任何点到 uu 的边被排除到残量网络以外

(严格来说只要大于等于 V|V| 即可。由于最短路一定是无环的,因此任意路径长最大是 V|V| )修改之后,只需要把正在研究的节点 uu 沿着刚才走的路退一步,然后继续搜索即可

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
int source;         // 源点
int sink; // 汇点
int p[max_nodes]; // 可增广路上的上一条弧的编号
int num[max_nodes]; // 和 t 的最短距离等于 i 的节点数量
int cur[max_nodes]; // 当前弧下标
int d[max_nodes]; // 残量网络中节点 i 到汇点 t 的最短距离
bool visited[max_nodes];

// 预处理, 反向 BFS 构造 d 数组
bool bfs() {
memset(visited, 0, sizeof(visited));
queue<int> Q;
Q.push(sink);
visited[sink] = 1;
d[sink] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) {
Edge &e = edges[(*ix)^1];
if (!visited[e.from] && e.capacity > e.flow) {
visited[e.from] = true;
d[e.from] = d[u] + 1;
Q.push(e.from);
}
}
}
return visited[source];
}

// 增广
int augment() {
int u = sink, df = __inf;
// 从汇点到源点通过 p 追踪增广路径, df 为一路上最小的残量
while (u != source) {
Edge &e = edges[p[u]];
df = min(df, e.capacity - e.flow);
u = edges[p[u]].from;
}
u = sink;
// 从汇点到源点更新流量
while (u != source) {
edges[p[u]].flow += df;
edges[p[u]^1].flow -= df;
u = edges[p[u]].from;
}
return df;
}

int max_flow() {
int flow = 0;
bfs();
memset(num, 0, sizeof(num));
for (int i = 0; i < num_nodes; i++) num[d[i]]++;
int u = source;
memset(cur, 0, sizeof(cur));
while (d[source] < num_nodes) {
if (u == sink) {
flow += augment();
u = source;
}
bool advanced = false;
for (int i = cur[u]; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
if (e.capacity > e.flow && d[u] == d[e.to] + 1) {
advanced = true;
p[e.to] = G[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if (!advanced) { // retreat
int m = num_nodes - 1;
for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix)
if (edges[*ix].capacity > edges[*ix].flow)
m = min(m, d[edges[*ix].to]);
if (--num[d[u]] == 0) break; // gap 优化
num[d[u] = m+1]++;
cur[u] = 0;
if (u != source)
u = edges[p[u]].from;
}
}
return flow;
}

最高标号预流推进(HLPP) 算法


算法思想

  • 预流推进算法将每个点看做一个可以存储流的“水池”,其中存有流的点称为活动节点
  • 对于每个非s或t的点,流入该点的流只可能有两个去向:流入汇点t,流回源点s;
  • 预流推进算法从源点开始沿边向其它点推流,之后每次选一个活动节点通过推流,试图使其变得不活动。当所有节点都是不活动节点时,算法就结束了;
  • 以上是传统预流推进算法的主要思想。而最高标号预流推进算法就是先预处理了一个距离标号h,通过优先队列,没次选出h最大的点进行推流,以减少重复操作,降低了复杂度。

算法步骤

  1. 通过 bfsbfs 预处理出距离标号 hh ,即到达汇点 tt最短距离;
  2. 将从源点s出发的边设为满流,到达的点 vv 标记为活动节点并加入到优先队列中;
  3. 从优先队列中不断取出点 uu 进行 推流 操作,要求到达点 vv必须满足 hu=hv+1h_u=h_v+1
  4. 若推流后 uu 中仍有余流,则进行重标号。将 huh_u 设为 min{hv}\min \{h_v\}再次加入优先队列并重复步骤 3.
  5. 当优先队列为时,结束算法

算法复杂度:O(n2m)O(n^2\sqrt m)!!!

Code :

1
/* www.google.com */

End.

坚持原创技术分享,您的支持将鼓励我继续创作!