DINIC

网络流之DINIC 算法 ~ HDU3459举例

Dinic算法引入了一个叫做分层图的概念。具体就是对于每一个点,我们根据从源点开始的bfs序列,为每一个点分配一个深度,然后我们进行若干遍dfs寻找增广路,每一次由u推出v必须保证v的深度必须是u的深度+1。下面给出代码

一些变量的定义

1
2
3
4
5
6
7
int s,t;//源点和汇点
int cnt;//边的数量,从0开始编号。
int Head[maxN];//每一个点最后一条边的编号
int Next[maxM];//指向对应点的前一条边
int V[maxM];//每一条边指向的点
int W[maxM];//每一条边的残量
int Depth[maxN];//分层图中标记深度

DINIC 主过程

1
2
3
4
5
6
7
8
9
10
int Dinic()
{
int Ans=0;//记录最大流量
while (bfs())
{
while (int d=dfs(s,inf))
Ans+=d;
}
return Ans;
}

BFS分层图过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool bfs()
{
queue<int> Q;//定义一个bfs寻找分层图时的队列
while (!Q.empty())
Q.pop();
memset(Depth,0,sizeof(Depth));
Depth[s]=1;//源点深度为1
Q.push(s);
do
{
int u=Q.front();
Q.pop();
for (int i=Head[u];i!=-1;i=Next[i])
if ((W[i]>0)&&(Depth[V[i]]==0))//若该残量不为0,且V[i]还未分配深度,则给其分配深度并放入队列
{
Depth[V[i]]=Depth[u]+1;
Q.push(V[i]);
}
}
while (!Q.empty());
if (Depth[t]==0)//当汇点的深度不存在时,说明不存在分层图,同时也说明不存在增广路
return 0;
return 1;
}

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 dist)//u是当前节点,dist是当前流量
{
if (u==t)//当已经到达汇点,直接返回
return dist;
for (int i=Head[u];i!=-1;i=Next[i])
{
if ((Depth[V[i]]==Depth[u]+1)&&(W[i]!=0))//注意这里要满足分层图和残量不为0两个条件
{
int di=dfs(V[i],min(dist,W[i]));//向下增广
if (di>0)//若增广成功
{
W[i]-=di;//正向边减
W[i^1]+=di;反向边加
return di;//向上传递
}
}
}
return 0;//否则说明没有增广路,返回0
}

DINIC 算法的优化

Dinic算法还有优化,这个优化被称为当前弧优化,即每一次dfs增广时不从第一条边开始,而是用一个数组cur记录点u之前循环到了哪一条边,以此来加速

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
//HDU 3459 举例代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
int n,m;
#define inf 100000000
#define MAXM 5000
#define MAXN 50
struct edg{int w,to,next;}x[MAXM+10];
int head[MAXN],cnt;
int vis[MAXN];
int cur[MAXN];/////////当前弧加速
void add(int u,int v,int w){
x[cnt].next=head[u]; x[cnt].to=v; x[cnt].w=w;
head[u]=cnt++;
x[cnt].next=head[v]; x[cnt].to=u; x[cnt].w=0;
head[v]=cnt++;
}
queue<int>q1;
int bfs(){
memset(vis,-1,sizeof(vis));
vis[1]=0;
q1.push(1);
while(!q1.empty()){
int now=q1.front();
q1.pop();
int j;
for(j=head[now];j!=-1;j=x[j].next){
if(vis[x[j].to]<0&&x[j].w){
vis[x[j].to]=vis[now]+1;
q1.push(x[j].to);
}
}
}
if(vis[n]<0)
return 0;
return 1;
}
int dfs(int u,int w){
if(u==n)
return w;
int j;
int ans=0;
//for(j=head[u];j!=-1&&ans<=w;j=x[j].next){
//for(int& j=cur[u];j!=-1&&ans<=w;j=x[j].next){/////当前狐加速//注意这里的&符号,这样i增加的同时也能改变cur[u]的值,达到记录当前弧的目的
for(j=cur[u];j!=-1&&ans<=w;j=x[j].next){
cur[u]=j;
if(vis[x[j].to]==vis[u]+1&&x[j].w){
int b=dfs(x[j].to,min(w-ans,x[j].w)); //流进去的有2个限制 min(总流量减去已经流掉的,可以流进去的)
x[j].w-=b;
x[j^1].w+=b; //cnt=0 开始 反向边下标=j^1 可以自己试试
ans+=b;
}
}
return ans;
}
/* j^1 举例
0 1 2 3 4 5
0 1 10 11 100 101
1 1 01 01 001 001
1 0 11 10 101 100
*/

int main(){
int t,ca;
scanf("%d",&t);
ca=1;
while(t--){
scanf("%d%d",&n,&m);
cnt=0;
memset(head,-1,sizeof(head));
int i,j;
for(i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
int ans=0;
while(bfs()){
for (int i=1;i<=n;i++)/////当前狐加速///每一次建立完分层图后都要把cur置为每一个点的第一条边
cur[i]=head[i];/////当前狐加速
ans+=dfs(1,inf);
}
printf("Case %d: %d\n",ca++,ans);
}
return 0;
}
文章目录
  1. 1. 网络流之DINIC 算法 ~ HDU3459举例
    1. 1.1. 一些变量的定义
    2. 1.2. DINIC 主过程
    3. 1.3. BFS分层图过程
    4. 1.4. dfs寻找增广路过程
    5. 1.5. DINIC 算法的优化