Dinic学习笔记

Dinic算法是一种用于网络流中最大流的增广路算法,其时间复杂度为$O(n^2 \times m)$,但大多数情况下会远远优于此时间复杂度。

基本概念

从Menci神犇的博客复制而来。我觉得这写的是很好的一篇介绍,除了代码风格不太喜欢。

  • 容量: ${capacity}(e)$ 表示一条有向边 $e(u,v)$ 的最大允许的流量。

  • 流量: ${flow}(e)$ 表示一条有向边 $e(u,v)$ 总容量中已被占用的流量。

  • 剩余容量(残量):即 $capacity(e)−flow(e)$,表示当前时刻某条有向边 $e(u,v)$ 总流量中未被占用的部分。

  • 反向边:原图中每一条有向边在残量网络中都有对应的反向边,反向边的容量为$0$,容量的变化与原边相反;『反向边』的概念是相对的,即一条边的反向边的反向边是它本身。

  • 残量网络:在原图的基础之上,添加每条边对应的反向边,并储存每条边的当前流量。残量网络会在算法进行的过程中被修改。

  • 增广路(augmenting path):残量网络中从源点到汇点的一条路径,增广路上所有边中最小的剩余容量为增广流量。

  • 增广(augmenting):在残量网络中寻找一条增广路,并将增广路上所有边的流量加上增广流量的过程。

  • 层次: $level(u)$ 表示节点 $u$ 在层次图中与源点的距离。

  • 层次图:在原残量网络中按照每个节点的层次来分层,只保留相邻两层的节点的图,满载(即流量等于容量)的边不存在于层次图中。

思路

用文字叙述大概如下:

1
2
3
4
1. 建立以出发点为源点的层次图(即源点到各店的距离)
2. 在层次图&残量网络中寻找增广路,并增广流量
3. 重复2直到找不到增广路
4. 重复123直到不存在层次图

实现

建立层次图使用bfs,而寻找增广路则是使用dfs递归增广。
具体实现的时候也有一定的技巧,在代码里面有注释。

反向边存在的意义是什么呢?形象来说其实就是给你一个后悔的机会,往一边流去之后还能再回来。注意反向边的容量在我这里初始为0。

有一个优化就是当前弧优化。这个优化是很显而易见的。如果这条边在当前层次图下找不到路,那么这条边在当前层次图内就再也不会用到。所以我们单开一个cur数组,记录目前遍历到的边,这样就可以进行优化。

代码

Luogu P3376为例

点击切换显示状态
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
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct Edge{
int from,to,flow,cap;
int next;
}edge[201000];
int fir[10100],dis[10100],cur[10100];

int n,m,s,t,tot = 2;//tot从2开始是最舒服的,既可以直接异或,后面的终止条件也不用想来想去。

bool bfs(){
queue<int> q;
memset(dis,0,sizeof(dis));
memcpy(cur,fir,sizeof(fir));//清空当前边
q.push(s);dis[s] = 1;
while(!q.empty()){
int nown = q.front();q.pop();
for(int nowe = fir[nown];nowe!=0;nowe = edge[nowe].next){
int v = edge[nowe].to;
if(dis[v] == 0 && edge[nowe].cap > edge[nowe].flow){
//两个条件:未遍历而且边可以增广
dis[v] = dis[nown]+1;
q.push(v);
//由于我们只沿最短路增广,所以这里就可以直接break掉了。
if(v == t)
return dis[t];
}
}
}
return dis[t];
}

int dfs(int nown,int limit = 0x3f3f3f3f){
//找到终点或没得可找 这个优化很重要
if(nown == t || limit == 0)
return limit;
for(int &nowe = cur[nown];nowe!=0;nowe = edge[nowe].next){
//这里有当前弧优化
int v = edge[nowe].to;
if(dis[v] == dis[nown]+1 && edge[nowe].flow < edge[nowe].cap){
//满足层次图条件(沿着最短路)
int f = dfs(v,min(edge[nowe].cap-edge[nowe].flow,limit));
if(f>0){
//更改当前边
edge[nowe].flow+=f;
edge[nowe^1].flow-=f;
return f;
}
}
}
return 0;
}

int dinic(){
int ans = 0,f;
while(bfs()){//bfs是步骤1
while( (f = dfs(s)) > 0)//dfs是步骤2
ans+=f;
}
return ans;
}

void addedge(int a,int b,int c){
edge[tot].from = a;edge[tot].to = b;
edge[tot].cap = c;edge[tot].flow = 0;
edge[tot].next = fir[a];fir[a] = tot;
tot++;
}

int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i = 0;i<m;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,0);//需要加反向边
}
printf("%d\n",dinic());
return 0;
}