网络最大流

任意一条网络流边可以描述为$x=(u,v,cap,flow)$。其中$u$为边的起点,$v$为边的终点,$cap$为流量限制,$flow$为当前流量……

网络流简介 (来自OI Wiki)

一 基础内容

任意一条网络流边可以描述为$x=(u,v,cap,flow)$。其中$u$为边的起点,$v$为边的终点,$cap$为流量限制,$flow$为当前流量。

  • 反向边:对于任意一条有向边$e=(i,j,cap,flow)$,定义$e’=(j,i,0,-flow)$ 为它的反向边。注意,反向边在网络流图中是不真实存在的,它其实是一个反悔机制,因此它的流量限制为$0$。定义反向边的当前流量与其对应的正向边的当前流量互为相反数。

反向边图解,图片来自网络:
1.2
图中,选择$u\to v$和$p\to v\to u\to q$两条增广路径,实际上等同于选择$u\to q$和$p\to v$两条增广路径。因为路径$u\to v$和它的反向边$v\to u$的流量之和总为$0$,同时被选中,则意味着这条边对实际流量其实是没有贡献的(这两条边的贡献等于流量之和,等于$0$)。实际上就变成了这两条边同时不被选中。

  • 残量网络:对于图上的任意一条边(包括反向边),定义它们的流量限制与当前流量之差为其残量。一张网络流图上所有边的残量构成残量网络。

  • 增广路:一条从原点($s$)到汇点($t$)的路径,并且这条路径上每条边(包括反向边)的残量均大于$0$。设$f_i$为这条路上最小的残量,那么这条增广路可以使得当前流量增加$f_i$。

  • 增广路定理:一张网络流图的流量达到最大流当且仅当残量网络中不存在增广路。

  • 最大流最小割定理:一张网络流图的最大流永远等于该图的最小割的总容量(蒟蒻的我不会证明)。对于割的定义,可以参考割点


二 Edmond Karp算法

1 流程

于是我们可以得出最朴素的最大流算法(Edmond Karp,EK算法)。

从原点开始,每次找一条到汇点的增广路径,并进行一次增广。

从原点出发向汇点搜索,设$m_i$为$s\to i$这条路上的最小残量$i$,$cap_e$为当前入边($e$)的流量限制,$flow_e$为当前入边的当前流量,可以得到递推式如下:
$$ m_i = \min m_j,cap_e-flow_e | e=(j,i),e \in E $$

每次到达汇点,将答案增广$m_t$,一直到残量网络中不存在增广路。于是就可以达到最大流。

注意反向边的储存。边表存图时,定义正向边编号为偶数,它的下一条边就是它的反向边。编号从$0$开始,则$i \text{xor} 1$总为$i$的对应边(正向边对应到反向,反向边对应到正向)。

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
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;
const int INF=0x7f7f7f3f;

//边表
class fs{
public:
int from,to; //起点,终点
int cap,flow; //cap容量上限,flow当前流量量
void init(int f,int t,int c,int fl){
from=f;
to=t;
cap=c;
flow=fl;
}
}E[CE];
vector<int> cde[CP]; //节点i的第j条边在E中的序号
int ecnt=0;
void add(int f,int t,int c){
E[ecnt].init(f,t,c,0);
E[++ecnt].init(t,f,0,0); //反向边
++ecnt;
cde[f].push_back(ecnt-2);
cde[t].push_back(ecnt-1); //反向边
}

int n,m,s,t;

//edmonds karp
int imp[CP]; //从起点出发的最小残量
int p[CP]; //搜索树上进入节点的边的编号

int Augment(int s,int t)
{
memset(imp,0,sizeof(imp));

queue<int>Q;
Q.push(s);
imp[s]=INF;

while(!Q.empty())
{
int cur=Q.front();
Q.pop();

for(int k=0; k<cde[cur].size(); k++) //遍历边表
{
fs e=E[ cde[cur][k] ];

if(!imp[e.to] && e.cap > e.flow)
{
p[e.to]=cde[cur][k];
imp[e.to] = min(imp[cur], e.cap-e.flow); //满足比起点的残量小
Q.push(e.to);
}
}
}

return imp[t];
}
int ek(int s,int t)
{
int maxf=0;
int aug=0;
while(aug=Augment(s,t)) //增广到无法增广为止
{
for(int cur=t; cur!=s; cur=E[p[cur]].from) //倒着搜索图
{
E[p[cur]].flow += aug;
E[p[cur]^1].flow -= aug; //反向边
}
maxf+=aug;
}
return maxf;
}

int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
}

printf("%d",ek(s,t));

return 0;
}

三 Dinic算法

在稠密图中,dinic算法的复杂度要比EK高到不知道哪里去了。

1 思想

dinic的主要思想是把一张网络流图分层,每次只往更深一层寻找增广路,以避免在同一层中绕圈子(这多半是无意义的)。
每当分层图中找不到增广路,这意味着当前图中至少有一条边的流量已经达到限制。也就是说这条边“断了”。而一条断了的边会改变图的分层情况,所以这时重新分层,并继续寻找增广路。
直到图上找不到一条$s\to t$的可行路径。也就是说所有道路都断了。此时会在图上会表现为找不到汇点的所在层级,因为根本没有到达汇点。说的更透彻一点,此时实际上是最小割被完全切断(最大流最小割定理)。

使用bfs完成图的分层,利用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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;

const int INF=0x7f7f7f3f;

//边表
class fs{
public:
int to,nxt; //终点和下一条边的编号
int cap,flow; //cap限制,flow当前流
fs() {cap=flow=to=0; nxt=-1;} //初始化为-1,因为边的下标从0开始
void init(int t,int n,int c,int f){
to=t; nxt=n; cap=c; flow=f;
}
}E[CE];
int hd[CP],ecnt;
void E_init(){
memset(hd,-1,sizeof(hd));
ecnt=0;
}
void _add(int x,int y,int z){
E[ecnt].init(y,hd[x],z,0);
hd[x]=ecnt++;
}
void add(int x,int y,int z){
_add(x,y,z);
_add(y,x,0); //反向建边
}

//variable define
int n,m,s,t;

//dinic
int dep[CP]; //节点深度

bool build(int s,int t) //bfs
{
memset(dep,0,sizeof(dep)); //首先清零
dep[s]=1; //原点深度为1

queue<int>Q;
Q.push(s);

while(!Q.empty()) //广搜
{
int u=Q.front();
Q.pop();

for(int k=hd[u]; k!=-1; k=E[k].nxt) //遍历边表
{
fs e=E[k];

if(e.cap-e.flow>0 && !dep[e.to]) //当前边没有断,且终点没被分层
{
Q.push(e.to);
dep[e.to]=dep[u]+1; //那么就给终点分层
}
}
}

return dep[t]>0; //判断汇点的深度是不是初始值
}
int Augment(int u,int t,int rst) //dfs :u 节点编号,rst 找到的最小残量
{
if(u == t) //已经到了汇点
return rst; //直接返回找到的最小残量

for(int k=hd[u]; k!=-1; k=E[k].nxt) //遍历边表
{
fs e=E[k];

if(e.cap-e.flow>0 && dep[u]==dep[e.to]-1) //还有残量,并且在下一层
{
int f=Augment(e.to,t, min(rst, e.cap-e.flow)/*从两个残量里面选一个小的*/);
if(f) //能增广则增广,因为反向边保留了退路
{
E[k].flow+=f;
E[k^1].flow-=f; //反向边
return f; //继续向上层递归返回增广量
}
}
}
return 0; //增广失败
}

int dinic()
{
int max_flow=0,f;
while(build(s,t)) //直到所有路径被切断
while(f=Augment(s,t,INF)) //直到不能增广(此处赋值语句兼用作判断真值),注意这里最小残量的初始值
max_flow+=f; //加上增广得到的解
return max_flow;
}

int main()
{
E_init();

scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}

printf("%d",dinic());

return 0;
}

3 优化

3-1 多路增广

上文中的代码一次搜索仅找出一条增广路,这样可能会在搜索时走很多重复的道路,造成一些常数负担。

所以每次在一条路上增广时,同时寻找多条增广路,直到干路的最小残量被用完或到达汇点时为止。这样可以避免重复走一条干路。
也就是说,一次dfs搜索所有的增广路。

3-2 当前弧优化

多路增广后,一条仍有残量却已经被增广的边是不可能继续被增广的,因为它所有的增广可能性已经被全部枚举了。所以继续dfs时,不需要再考虑这些边。所以设$cur_i$为新的边表表头,即以$i$为起点且没有被增广过的第一条边的编号,每次增广后更新$cur_i$即可。
注意,每次重新构造分层图后,$cur_i$需复原,因为此时对于 任意一条边 的 任意一种增广可能性 都没有考虑。

3-3 实现

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

const int CP=1e4+4;
const int CE=2e5+5;

const int INF=0x7f7f7f3f;

//边表
class fs{
public:
int to,nxt,cap,flow;
fs() {to=cap=flow=0; nxt=-1;}
void init(int t,int n,int c,int f){
to=t; nxt=n; cap=c; flow=f;
}
}E[CE];
int hd[CP],ecnt=0;
int cur[CP]; //当前弧优化,用来保存从i出发未增广的第一条边在边表中的下标
void E_init(){
memset(hd,-1,sizeof(hd));
ecnt=0;
}
void _add(int x,int y,int z){
E[ecnt].init(y,hd[x],z,0);
hd[x]=ecnt++;
}
void add(int x,int y,int z){
_add(x,y,z);
_add(y,x,0); //反向边
}

//variable define
int n,m,s,t;

void copy(int* a,int* b,int lenth){ //复制a[]到b[]中
for(int i=0;i<=lenth;i++)
b[i]=a[i];
}

//dinic
int dep[CP];

bool build(int s,int t) //构造分层图
{
memset(dep,0,sizeof(dep));
dep[s]=1;

queue<int>Q;
Q.push(s);

while(!Q.empty())
{
int u=Q.front();
Q.pop();

for(int k=hd[u]; k!=-1; k=E[k].nxt)
{
fs e=E[k];

if(!dep[e.to] && e.cap-e.flow>0)
{
dep[e.to]=dep[u]+1;
Q.push(e.to);
}
}
}

return dep[t]>0;
}

int Augment(int u,int t,int rst) //多路增广
{
if(u == t) //到达汇点
return rst; //返回最小残量

int used=0; //已经得到的增广量
for(int k=cur[u]; k!=-1; k=E[k].nxt) //当前弧优化
{
cur[u]=k; //重新记录第一条边,赋值为k是因为这条边目前为止还未增广
fs e=E[k];

if(dep[e.to]==dep[u]+1 && e.cap-e.flow>0)
{
int f=Augment(e.to,t, min(rst-used, e.cap-e.flow));
if(f)
{
used+=f; //累加增广量
E[k].flow+=f;
E[k^1].flow-=f;
if(used == rst) //增广路的残量用完了
return used; //返回增广量
}
}
}

return used; //搜索完毕,返回增广量
}
int dinic()
{
int max_flow=0;
while(build(s,t))
{
copy(hd,cur,n); //复制cur的初始边
max_flow += Augment(s,t,INF); //一次完成所有增广
}
return max_flow;
}

int main()
{
E_init();

scanf("%d%d%d%d",&n,&m,&s,&t);
while(m--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}

printf("%d",dinic());

return 0;
}
作者

ce-amtic

发布于

2019-02-23

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×