网络流

网络流是一种类比于水流,找出源点到汇点最大流量的一类问题。

先来看一个经典的网络流问题(HDU1532):

每当约翰的田里下雨,贝西最喜欢的三叶草地里就会形成一个池塘。这意味着三叶草被水覆盖了一段时间,需要很长时间才能重新生长。因此,农夫约翰建了一套排水沟,这样贝西的苜蓿地就不会被水覆盖了。相反,水就会被排到附近的小溪。作为一名一流的工程师,农夫约翰还在每条水沟的开头安装了调节器,这样他就能控制水流进水沟的速度。农夫约翰不仅知道每分钟每条沟渠能输送多少加仑的水,还知道沟渠的精确布局,这些沟渠从池塘里流出,相互流入,形成一个潜在的复杂网络。根据所有这些信息,确定水从池塘中进入小溪的最大速度。对于任何给定的沟渠,水只朝一个方向流动,但可能有一种方式可以让水在一个圆圈中流动。
多组输入。对于每种情况,第一行包含两个空格分隔的整数,$N (0 \leq N \leq 200)$和$M (2 \leq M \leq 200)$。N是农民约翰挖的沟的数目。$M$是这些沟渠的交叉点个数。节点1是池塘。节点$M$是汇点。下面$N$行中的每一行都包含三个整数,$Si$、$Ei$和$Ci$。$Si$和$Ei$ $(1 \leq Si, Ei \leq M)$表示该沟渠流经的两个节点。水将通过这条沟从$Si$流到$Ei$。$Ci (0 \leq Ci \leq 10^7)$是水流通过沟渠的最大速度。
对于每组样例,输出一个整数,即从池塘中排空水的最大速度。
样例输入:

1
2
3
4
5
6
7
> 5 4
> 1 2 40
> 1 4 20
> 2 4 20
> 2 3 30
> 3 4 10
>

样例输出:

1
2
> 50
>

对于网络流问题,本文使用 $Dinic$ 算法来讲解。

Dinic算法

Dinic算法的大致步骤为:

  1. 对于一个已经建好边的图,我们需要对每一条边都取反建一条反边,其流量为0。
  2. 对当前图跑一边BFS,确定每个可达点(流量不为0)的层次(即距离源点的远近关系),如果到达不了汇点,则跳转至4。此图一般叫做层次图。
  3. 对已确定关系的图跑一次DFS,找出一条从源点到汇点的水流,若找到,继续执行3,否则,跳转至2。
  4. 输出总和。
  5. (弧优化)

每一步作用为:

1. 建反边

建立反向边的意义为为了保证贪心的过程是正确的,假如不建立反向边,贪心的策略可能会发生错误,可以认为反向边是为了容错。这一点可以参考白书$p210,p211$ 。

1
2
3
4
5
6
void add(ll from,ll to,ll dis){
G[cnt].to=to;
G[cnt].dis=dis;
G[cnt].nxt=head[from];
head[from]=cnt++;//此处使用链式前向星存图
}

2. BFS

找出贪心的顺序,$Dinic$ 算法就是每次找出一条最短的增广路,因此需要$BFS$ 将每个点的层次计算出来,方便接下来进行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bfs(){
memset(d,-1,sizeof(d));//初始化均不可达
queue<ll>que;
que.push(s);
d[s]=0;
while(!que.empty()){
ll u=que.front();que.pop();
for(ll i=head[u];i!=-1;i=G[i].nxt){
ll v=G[i].to;
if(d[v]==-1 && G[i].dis>0){//联通(有流量)且之前未到达
d[v]=d[u]+1;
que.push(v);
}
}
}
}

3. DFS

对于每一次$BFS$ ,使用 $DFS$ 将现在的层次图中所有的增广路全部找出来(榨干)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll dfs(ll u,ll flow){//flow为u之前增广路上所有的边的最小值,因为一条路径的流量即为这条路径上的最小值
if(u==t) return flow;
ll x=0;
for(ll i=cur[u];i!=-1;i=G[i].nxt){
cur[u]=G[i].nxt//此处为弧优化,接下来会讲
ll v=G[i].to;
if(d[v]==d[u]+1 && G[i].dis>0){//向下增广
ll res = dfs(v,min(flow,G[i].dis));
flow -= res;
x += res;//x为当前节点向下能够增广的最大流量

G[i].dis -= res;//找到增光路后,路径上的每一条边都要减去flow,其反向边都要加上flow
G[i^1].dis += res;//cnt从0开始计数,每条边与其反向边只有最低为不相同,因此^1即为反向边
if(flow == 0) break;//flow=0即为已经将这条路径前半部分全部使用完毕,不能够再继续使用了
}
}
if(!x) d[u]=-1;//如果当前点到达不了汇点,那么以后就不走这个点了
return x;
}

4. 输出总和

如题。

1
2
3
4
5
6
7
8
9
10
void dinic(){
ll max_flow=0;
while(true){
bfs();//层次图
if(d[t]==-1) break;
for(ll i=1;i<=n;i++) cur[i]=head[i];//弧优化
max_flow+=dfs(s,INF);//计算流量
}
printf("%lld\n",max_flow);
}

5. 弧优化

如果是单纯的$dfs$,会浪费许多时间在已经遍历过的边上,对于一些已经被访问过或已经被榨干的边,我们在$DFS$ 的过程中就不需要再去访问,因此我们用 $cur[\space]$ 数组去存储当前节点接下来应该访问的节点,不需要再花费时间在那些无用的节点上。

完整代码如下:

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=0x3f3f3f3f;
const ll maxn=1000000+10;
ll n,m,s,t,u,v,w;
ll cnt;
struct edge{
ll to,dis,nxt;
}G[maxn];
ll head[maxn],d[maxn],cur[maxn];
void add(ll from,ll to,ll dis){
G[cnt].to=to;
G[cnt].dis=dis;
G[cnt].nxt=head[from];
head[from]=cnt++;
}
ll dfs(ll u,ll flow){
if(u==t) return flow;
ll x=0;
for(ll i=cur[u];i!=-1;i=G[i].nxt){
cur[u]=G[i].nxt;
ll v=G[i].to;
if(d[v]==d[u]+1 && G[i].dis>0){
ll res = dfs(v,min(flow,G[i].dis));
flow -= res;
x += res;
G[i].dis -= res;
G[i^1].dis += res;
if(flow == 0) break;
}
}
if(!x) d[u]=-1;
return x;
}
void bfs(){
memset(d,-1,sizeof(d));
queue<ll>que;
que.push(s);
d[s]=0;
while(!que.empty()){
ll u=que.front();que.pop();
for(ll i=head[u];i!=-1;i=G[i].nxt){
ll v=G[i].to;
if(d[v]==-1 && G[i].dis>0){
d[v]=d[u]+1;
que.push(v);
}
}
}
}
void dinic(){
ll max_flow=0;
while(true){
bfs();
if(d[t]==-1) break;
for(ll i=1;i<=n;i++) cur[i]=head[i];
max_flow+=dfs(s,INF);
}
printf("%lld\n",max_flow);
}
int main()
{
while(~scanf("%lld %lld",&m,&n)){
s=1,t=n;
memset(head,-1,sizeof(head));
cnt=0;
for(ll i=0;i<m;i++){
scanf("%lld %lld %lld",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
dinic();
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------