网络最大流算法能在信息学竞赛中处理很多问题，而且往往是不可被其它算法替代的。而最大流算法则是处理问题的方法之一。本文将介绍网络最大流的算法及其优化。
前言
本文发表于：
网络最大流算法能在信息学竞赛中处理很多问题，而且往往是不可被其它算法替代的。而最大流算法则是处理问题的方法之一。本文将介绍网络最大流的算法及其优化。
关于本文代码
网络最大流算法-Dinic
前置知识
几个概念
- 源点（$S$)：网络流流出的点
- 汇点（$T$)：网络流流入的点
- 流量：一条边上流过流的多少
- 容量：一条边最大流量
- 残量：一条边上剩余流量，即容量$-$流量
朴素的算法
由于网络流算法都是基于增广这一思路的，接下来对增广进行介绍。
要想求出网络最大流，思路大体上就是不停地寻找增广路，直到没有增广路，即可保证求到了最大流。
增广：
1.找到一条从源点通向到汇点的路径，并且这条路径上，每条边都有残量（这代表这条路并没有流满，完全可以增加一些流量），这条路叫做增广路。
2.取这条增广路上残量最小值，代表这条增广路上可以增加这么多流量（取最小值的原因显然）。
3.将增广路上每条边残量减去增加的流量，加入答案；
4.直到找不到增广路。
HACK
如果仔细思考，以上算法仍然存在缺陷：
如下图：
此时找到的最大流是$10$，而实际上是$15$，因此，我们要进行改进。
改进
这里是解决网络流问题的关键步骤：
引入反向边
即每次在找到增广路，更新残量时，同时将其反向边的残量相应增加：
具体过程如下图：
这样求出的最大流是15，正确。
实际上，引入了反向边，让程序可以进行一次$S-3-4-1-2-T$这样的增广。
第一次增广不一定能寻得恰当的路线，而反向边可以让程序有反悔的机会，便是对的。
效率
这样多次进行增广，会导致程序效率便得非常低。例如下图：
会增广很多次。于是我们引入Dinic算法。
Dinic
$\text{Dinic}$在原有算法基础上，增加了分层图，即根据距离源点的距离，将每个点进行深度标号，每次找增广路时都保证深度递增地寻找。
分层（BFS）
以下是分层部分的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| bool Bfs()
{
queue<int> q;
memset(dep,0,sizeof(dep));
dep[S]=1;
q.push(S);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(w[i] && !dep[v])
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[T];
}
|
增广（DFS）
以下是找增广路部分的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int Dfs(int u,int dis)
{
if(u==T || (!dis)) return dis;
int sum=0;
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(dep[v]==dep[u]+1 && w[i])
{
int di=Dfs(v,min(dis,w[i]));
if(di>0)
{
w[i]-=di,w[i^1]+=di;
return di;
}
}
}
return 0;
}
|
调用部分
1
2
3
4
5
6
7
8
9
| int Dinic()
{
int ans=0;
while(Bfs())
{
ans+=Dfs(S,10000000);
}
return ans;
}
|
主函数
需要注意的是，为了实现增加反边，在建图时就需要提前建好容量为$0$的反边。
补充
在链式前向星建图中，$cnt$初始值设成$1$,这样对于编号为$i$的边，它的反边编号就是$i$^$1$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int main()
{
cnt=1;
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
Add(x,y,z);
Add(y,x,0);
}
printf("%d\n",Dinic());
return 0;
}
|
Dinic的优化
以上的$\text{Dinic}$算法是优化前的，一下对它的$3$种优化进行一一介绍：
当前弧优化
在每次增广后，某个节点引出的几条边的残量会被更新成$0$，在原有算法中，残量为$0$的边仍会被扫一遍，而当前弧优化即是对上次停下的位置进行记录，下次直接从上次结束的位置开始。
实现方法就是用一个数组记录每个点处理到了第几条边，在代码中只需要加入几行即可，如下：
增广（DFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int cur[N];
int Dfs(int u,int dis)
{
if(u==T || (!dis)) return dis;
for(int &i=cur[u];i;i=next[i])
{
int v=to[i];
if(dep[v]==dep[u]+1 && w[i])
{
int di=Dfs(v,min(dis,w[i]));
if(di>0)
{
w[i]-=di,w[i^1]+=di;
return di;
}
}
}
return 0;
}
|
调用部分
1
2
3
4
5
6
7
8
9
10
| int Dinic()
{
int ans=0;
while(Bfs())
{
memcpy(cur,head,sizeof(head));
ans+=Dfs(S,10000000);
}
return ans;
}
|
多路增广
每次不只是找一条增广路，而是只要可以就都递归下去，这样增广出来的不只是一条链，而是一个网，可以加快运行速度（降低常数）
增广部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int Dfs(int u,int dis)
{
if(u==T || (!dis)) return dis;
int flow=0;
for(int i=cur[u];i;i=next[i])
{
cur[u]=i;
int v=to[i];
if(dep[v]==dep[u]+1)
{
int di=Dfs(v,min(dis,w[i]));
flow+=di;
dis-=di;
w[i]-=di,w[i^1]+=di;
if(!dis) break;
}
}
return flow;
}
|
炸点
当一个点连的边的残量都为$0$时，这个点已经没有用了，之后就不要再进入这个点了，这就是“炸点”。
具体实现可以把这个点的深度设置成$-1$，保证不会再次访问这个点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int Dfs(int u,int dis)
{
if(u==T || (!dis)) return dis;
int flow=0;
for(int i=cur[u];i;i=next[i])
{
cur[u]=i;
int v=to[i];
if(dep[v]==dep[u]+1)
{
int di=Dfs(v,min(dis,w[i]));
flow+=di;
dis-=di;
w[i]-=di,w[i^1]+=di;
if(!dis) break;
}
}
if(!flow)
dep[u]=-1;
return flow;
}
|
总结
Dinic算法是较为高效的网络流算法，建议使用时加入以上$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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define next adjagag
using namespace std;
const int N=1000010;
int head[N],to[N],next[N],w[N];
int cnt=1;
int n,m,S,T;
void Add(int x,int y,int z)
{
to[++cnt]=y;
w[cnt]=z;
next[cnt]=head[x];
head[x]=cnt;
}
int dep[N];
bool Bfs()
{
queue<int> q;
memset(dep,0,sizeof(dep));
dep[S]=1;
q.push(S);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(w[i] && !dep[v])
{
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[T];
}
int cur[N];
int Dfs(int u,int dis)
{
if(u==T || (!dis)) return dis;
int flow=0;
for(int i=cur[u];i;i=next[i])
{
cur[u]=i;
int v=to[i];
if(dep[v]==dep[u]+1)
{
int di=Dfs(v,min(dis,w[i]));
flow+=di;
dis-=di;
w[i]-=di,w[i^1]+=di;
if(!dis) break;
}
}
if(!flow)
dep[u]=-1;
return flow;
}
int Dinic()
{
int ans=0;
while(Bfs())
{
memcpy(cur,head,sizeof(head));
ans+=Dfs(S,10000000);
}
return ans;
}
int main()
{
cnt=1;
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
Add(x,y,z);
Add(y,x,0);
}
printf("%d\n",Dinic());
return 0;
}
|
参考资料
https://www.cnblogs.com/SYCstudio/p/7260613.html
