洛谷 3376 【模板】网络最大流 Ford-Fulkerson算法

缘起

开始学习网络流相关算法. 首先拿 Ford-Fulkerson算法 开刀. 洛谷 3376 【模板】网络最大流

分析

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
题目描述
如题，给出一个有向图，以及其源点和汇点，求出其网络最大流。

输入格式
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）

输出格式
一行，包含一个正整数，即为该网络的最大流。

输入输出样例
输入 #1复制
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
输出 #1复制
50
说明/提示
时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=25

对于70%的数据：N<=200，M<=1000

对于100%的数据：N<=10000，M<=100000

样例说明：
1
2
3
4
5
6
7
8
9
题目中存在3条路径：

4-->2-->3，该路线可通过20的流量

4-->3，可通过20的流量

4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）

故流量总计20+20+10=50。输出50。

首先来介绍一下网络流中的最大流问题.

1
2
3
给定一个有向图G=(V,E)，把图中的边看作管道，每条边上有一个权值，表示该管道的流量(即几加仑/秒)上限。
给定源点s和汇点t，现在假设在s处有一个水源， t处有一个蓄水池，
问从s到t的最大水流量是多少?

关于网络流的最大流问题的严格数学论证可以参见圣经《算法导论》第26章（我看完了，清晰易懂）. 这里不打算铺开. 因为那样会显得很乏味. 本文依旧采用意识流（但是抓住思想主线）的叙事手法来论述FK算法.

首先，我们要这么看网络流问题. 学过图论的同学都知道，原先我们处理过最短路问题. 那个时候边的权重的含义是路径的长度. 所以最短路径问题回答的是”一个城市到另一个城市之间最短路径的问题”. 而网络流问题将边的权的意义变更为物料流动的速率（例如一根管道每小时最多流过200加仑的原油，或者一根电缆可以经受20安培的电流.） 而且注意, 除了流网络中的源（source）和汇（sink），物料是不会在任何一个顶点积累或者聚集的. 所以流网络中除了源和汇的其他任何点都会满足电学中的Kirchhoff守恒定律——即除了源和汇的任何节点, 流入总量=流出总量

在继续前进之前, 我们先来介绍一些关于网络流的基本概念. 

1
2
3
4
G=(V,E)是有向图. 每条弧(u,v)上的权重c(u,v)是此弧的容量. f(u,v)是此弧上的流量.
即c(u,v)是最大可通行的量（例如一根水管最多就只能承受20加仑/小时的输送速率,已是极限）
而f(u,v)是最终实际输送的速率(例如,最终只是15加仑/小时)
则对任何(u,v), 0<=f(u,v)<=c(u,v)

好的，介绍完网络流问题的背景之后, 我们回到最初提出的网络流的最大流问题上来. 如果你不知道FK算法的话，你最先想到的算法是什么? 贪心!

怎么贪心呢?

1
2
3
4
5
基本思路很简单,每次用dfs从源到汇找一条可行路径(如果一条路径上容量已经用光了,则此路不通,将该路径从有向图
中抹去)，这条路径上容量最小的那条边的容量，就是这次dfs所找到的流量。
然后对于路径上的每条边，其容量要减去刚才找到的流量(表示还剩下这么多容量可以提供)。
这样，每次dfs都可能增大流量，直到某次dfs找不到可行路径为止，
最大流就求出来了

这个思想是否正确?

不正确, 看下图（s和源，t是汇， 后面都是这样）

第一次dfs找到的路径是 s->a->b->t, 则最大流+=100. 然后这条路径上所有的弧的容量减去100， 得到（我们将容量为0的弧去掉了）

从上图就无法再找到一条路径了. 所以贪心算法得到的最终答案是 100 为最大流. 但是这显然是不正确的. 因为

s->a->t 和 s->b->t 这两条路径就能提供200的流. 这才是最大流.

那么上述贪心算法的弊病在哪里? 导致了求解的不正确?

在将 b->t 过早的抹去了. 导致我们无法发现 s->b->t 这条路径——至少表面上看是这样.

Ford-Fulkerson算法（简称FK，下同）它也是每次不断的dfs找路. 但是区别在于每次dfs完毕之后构造残余网络. 然后下次总是在上一次dfs完构造的残余网络上进行dfs找路.

构造残余网络的目的是提供修正上一次dfs可能带来的错误（就像上面贪心那样可能错误的提早的抹去了一些弧）

残余网路是什么?

1
2
3
残余网络是, 对于原图的弧(u,v,c). c是弧的容量, u,v是弧的起点和终点. 找到了流量f. 则我们就将此弧改成(u,v,c-f). 这并不难理解. 因为你用掉了f的容量嘛~ 剩下的可提供的容量自然就是c-f咯~ 难理解的是, FK算法还要求你增加一条弧(v,u,f). 即反向弧. 弧的容量恰好就是此次你找到的流量f.

然后就在残余网络上继续dfs找下一条路径.直至再也找不到为止.  这就是FK算法的全部了.

ps: 哦，忘说了, 在残余网络中dfs找路找到的s到t的路叫做增广路径（augmentation）. 增广的汉语解释就是增大，和英文的augment是一样的. 即通过这条路径，我们就能继续增大流的值.

综上, 其实正确的FK算法相比错误的贪心算法唯一的区别就在于dfs找路完毕之后多了一个收尾工作——构造残余网络，然后下一次dfs是在残余网络上dfs,而不是在原网络上. 而构造残余网络相比贪心算法中dfs完毕处理原网络也就是多了一步——增加反向弧.

为什么需要添加一条反向弧?

严格的数学论证参见算导. 那里的证明是构造性的——即证明如果在残余网络中能找到一条s到t的路径的话，则可以构造出新的流，这个流的值严格大于原先的流. 即增广了原先的流.

这里只给形象但不失重点的解释

假设我们dfs找到了一条a->b 的流量为f的路(假设a->b的容量为c). 则按照FK算法的处理. 我们应该将上图变为

注意上图多出来的的(f,0)的反向弧（这是FK算法的核心）.如果我们在上图又通过dfs找到了一条新路，流量为f-k

即第二次dfs找到的路径是 ①->②->③, 流量为f-k（0<=k<f）. 其中②是反向弧. 则我们就知道上图可以得到从s到t的流的值是

f+f-k>f

看到了吗? 流入的f在a出分叉, 一部分为k流向b, 一部分为f-k. k的那部分和底部左边的f-k在b节点交汇, 汇成f的流量流向t.

所以我们通过反向弧找到了一条增广路径，然后这条增广路径能增广我们的流量，增广的值恰好就是增广路径的流量f-k>0

算导上对反向弧的意义讲的一针见血——反向弧其实就是将上次dfs一股脑推过来的流量后面dfs的时候发现有更优的方案, 所以退回去了一些（所以不能超过上次dfs推过来的流量f, 所以反向弧的容量才是f） 例如上面的例子中，一开始第一次dfs一股脑的推来了f的流量, 但是最后呢? 退回去了f-k的流量（反向弧的流量），实际最后的最大流方案是a->b仅仅跑f-(f-k)=k的流量而已.

所以总结一下FK算法的框架

1
2
3
4
5
残余网络伊始是原图,即零流的残余网络
while(能在残余网络上dfs找到从s到t的增广路径（容量为0的弧是不能通过的）,进而得到流量f,ans+=f)
{
	按照上面说的方法（2步, 第一步, 原弧容量减去流量f, 第二步反向弧容量+f）更新残余网络
}

为什么找不到增广路径的时候就一定已经得到最大流了呢? 要证明这一点, 需要引入新的概念——最小割. 《算导》的定理26.6证明了最大流等价于最小割等价于残余网络没有增广路径. 细节就不说了.

最后，我们来看看FK算法的复杂度问题. 显然，每次dfs的复杂度是O(|E|). 假设最大流是F. 而FK算法每次dfs最少增加流量1, 所以FK算法的复杂度是 O(F*|E|)

但是这其实是一个很松的上界. 最坏复杂度一般实际运用时几乎不会碰到的. 除非题目有意设计一些比较极端的数据. 例如下图

按照FK算法，如果你运气不好，先找到 ①->②->③, 则②反向, ①和③变成99, 而下次dfs找到的是 ④->②->⑤

然后②再反向，④和⑤都变成99, 第三次dfs找到的是①->②->③，②反向, ①和③都变成98….. 如此这般继续下去. 最后我们需要dfs 200次, 每次增广1的流量, 才能得到最大流为200！ 但实际上，运气好的话，只需要dfs两次（第一次①->⑤, 然后①和⑤反向, 第二次④->③）就能得到最大流200.

FK怎么会这样? 怎么能避免这种低效情况的发生?

在每次增广的时候，选择从源s到汇t的具有最少边数的增广路径,即不是通过dfs寻找增广路径，而是通过bfs寻找增广路径。这就是Edmonds-Karp 最短增广路算法（简称EK）已经证明这种算法的复杂度上限为|V|*|E|^2

效率比FK高.

EK和FK相比, 唯一的区别在于改进了在残余网络上寻找增广路径的算法——FK是dfs，而EK是bfs. 仅此而已. EK后面我会继续写文章论述的.

好的，回到本题. 本题的唯一意义就是敲一个正确无误的FK的板子.

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
//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000") // 必须手工扩栈, 不然爆栈被T
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 10005, maxm = 100005, inf = 0x3f3f3f3f;

int n,m,s,t,head[maxn],cnt;
bool v[maxn]; // dfs 用的哈希数组

struct Arc
{
	int from,to,nxt,cap; // 从from到to的弧容量是cap
}g[maxm<<1];

void addArc(int u, int v, int w)
{
	g[cnt].from = u, g[cnt].to = v, g[cnt].nxt = head[u], g[cnt].cap = w;
	head[u] = cnt++;
	g[cnt].from = v, g[cnt].to = u, g[cnt].nxt = head[v], g[cnt].cap = 0; // 初始化反向弧（即0流的反向弧容量为0）
	head[v] = cnt++;
}

int dfs(int cur, int t, int f) // cur是当前节点, t是汇, f是当前路径中的弧的容量的最小值(如果能到达t, 则f就是此次dfs找到的增广流量)
{
	if (cur==t)
	{
		return f; // fk的每次dfs都是找到了就不玩了的, 所以没必要改回来, 又不是得到所有的路径(例如全排列). 因为如果一个点u后面搜所有的路径都搜不到, 则再次搜到u你根本不需要再搜.所以v[u]变成true了就不用改回来了
	}
	v[cur] = true;
	for (int h = head[cur],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!v[to] && g[h].cap>0) // 容量>0才能走, 否则此路不通
		{
			int d = dfs(to, t, min(f, g[h].cap)); // 更新当前路径中的最小容量, 继续dfs找增广流量
			if (d>0) // 找到了就不玩了, 但是在退出之前, 要更新残余网络
			{
				g[h].cap-=d; // 当前弧的容量-d
				g[h^1].cap+=d; // 反向弧的容量+d
				return d;
			}
		}
	}
	return 0; // 如果都找不到, 返回0
}

int fk(int s, int t) // 源s到汇t的最大流
{
	int ans = 0;
	while(1)
	{
		memset(v, 0, sizeof(v));
		int d = dfs(s,t,inf); // 每次dfs得到的增广路径d
		if (d<=0) // 找不到增广路径了
		{
			return ans;
		}
		ans+=d;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	memset(head, -1,sizeof(head));
	scanf("%d%d%d%d", &n,&m,&s,&t);
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d", &u, &v, &w);
		addArc(u,v,w); // 初始化残余网络(即0流的残余网络)
	}
	printf("%d\n", fk(s,t));
	return 0;
}

ac情况

1
2
3
4
评测状态
Accepted
评测分数
100

这里再说一下上面dfs搜索路径没搜到不需要改回来. 但是同样是搜索路径，【1】中却要改回来. 他俩的本质不同是前者是找到了, 就不玩了. 所以不玩了，你再改回来或者不改回来都无所谓了（因为都return掉了）. 但是如果没找到. 前者是不需要改回来的，而后者是需要改回来的. 因为后者是要求出所有路径, 而前者只要找一条. 就像代码第31行注释说的那样——如果一点出发开始dfs找不到的话，不需要改回来，因为你再次搜到这个点的时候, 你还用去搜它吗? 显然不需要. 因为这个true已经告诉你沿此点搜索你是到达不了目的地的.

但是你看看【1】中的代码是怎么写的

1
2
3
4
5
6
if (!book[x->v])
			{
				book[x->v] = true; // 锁定
				dfs(x->v, distance+x->w, path, len+1); // 注意, distance+x->w 而不能distance+=x->w, 因为在本轮中 distance是不能变的
				book[x->v] = false; // 解锁
			}

注意第四行——它包含了搜到和没搜到两种结果. 如果没搜到，当然不需要改回来，理由已经说了. 如果搜到了呢? 即从x->v出发能搜到目的地呢? 那你能不改回来吗? 显然不能，因为完全可能从x->v出发有不止一条路径抵达目的地. 如果你不改回来, 就错失了另一条. 这就是本题和【1】的细微差别. 对于理解dfs的本质是重要的.

参考

【1】https://yfsyfs.github.io/2019/05/27/%E4%BD%BF%E7%94%A8dfs%E6%B1%82%E8%A7%A3%E6%9C%89%E5%90%91%E7%BD%91%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84/