网络流算法总结

最大流算法

该算法主要求的是,在一个有向图中,每条边上有一个最大流量,求从源点到汇点的最大流量。一般求解这类问题主要有以下几种算法。

增广路EK算法

这个算法的主要思想很简单,就是不断bfs寻找增广路并往里头添加流量,直到无法搜出增广路,此时从源点流出的流量即为最大流。注意其中的反流量概念,即\(flow[u][v]=-flow[v][u]\)
该算法时间复杂度上限为\(O(V*E^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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=1e+9;
const int maxn=200+10;
int c[maxn][maxn],f[maxn][maxn],p[maxn],pre[maxn],d[maxn<<4];
int main(){
int i,j,k,m,n;
int x,y,z;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
c[x][y]+=z;
}
int flag=1;
while(flag){
flag=0;
memset(p,0,sizeof(p));
int s=0,t=1;d[1]=1;pre[1]=0;p[1]=1;
while(s<t){
s++;x=d[s];
for(i=1;i<=n;i++)
if(!p[i] && (c[x][i]>f[x][i] || f[i][x]>0)){
p[i]=1;
d[++t]=i;
pre[i]=x;
if(i==n){
flag=1;
break;
}
}
if(flag)break;
}
if(!flag)break;
t=n;int min=INF;
while(pre[t]){
x=pre[t];
y=t;
if(c[x][y]>f[x][y] && c[x][y]-f[x][y]<min)
min=c[x][y]-f[x][y];
else if(f[y][x]>0 && f[y][x]<min)
min=f[y][x];
t=pre[t];
}
t=n;
while(pre[t]){
x=pre[t];
y=t;
if(c[x][y]>f[x][y])
f[x][y]+=min;
else if(f[y][x]>0)
f[y][x]-=min;
t=pre[t];
}
}
int ans=0;
for(i=1;i<=n;i++)
ans+=f[1][i];
printf("%d\n",ans);
return 0;
}

dinic算法

与EK算法不同的是,dinic算法每次要对有向图进行一次bfs,对这张图进行分层,得到图上的每一个点的层数。再进行dfs搜索增广路,增广路只能从这一层到下一层。若不存在增广路,则重复上述过程,对这张图重新分层,直到无法搜到增广路为止。
该算法的时间复杂度的理论上限为\(O(n^2m)\),不过同样地,一般到不了这个复杂度。甚至在用dinic算法做二分图匹配时,复杂度能到\(O(\sqrt{n}*m)\)。
下面附上代码:

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
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int maxm=1e5+10;
const int maxn=1e4+10;
int nex[maxm<<1],beg[maxm<<1],to[maxm<<1],flow[maxm<<1],q[maxn],lev[maxn];
int e=1,n;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y,int z){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
flow[e]=z;
}
int bfs(int s,int t){
int f=0,l=1,i;
memset(lev,0,sizeof(lev));
lev[s]=1;
q[1]=s;
while(f<l){
f++;
int x=q[f];
if(x==t)return 1;
for(i=beg[x];i;i=nex[i])
if(!lev[to[i]] && flow[i]>0){
lev[to[i]]=lev[x]+1;
q[++l]=to[i];
}
}
return 0;
}
int dfs(int x,int goal,int maxflow){
int i;
if(x==goal)
return maxflow;
for(i=beg[x];i;i=nex[i])
if(flow[i]>0 && lev[x]+1==lev[to[i]]){
int tmp=dfs(to[i],goal,min(maxflow,flow[i]));
if(tmp>0){
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
}
return 0;
}
int main(){
int i,j,k,m;
int x,y,z,s,t;
n=read();m=read();s=read();t=read();
for(i=1;i<=m;i++){
x=read();y=read();z=read();
add(x,y,z);
add(y,x,0);
}
int ans=0;
while(bfs(s,t))
ans+=dfs(s,t,INF);
printf("%d\n",ans);
return 0;
}

ISAP算法

ISAP算法则在dinic算法的基础上又进行了一些优化。dinic算法需要对残余流量进行多次分层,而ISAP只需要进行一次,甚至你可以不进行预处理分层(如下文中的代码就没有预处理分层)。dinic算法在増广后遇到没有满足条件的增广路后,会对残余流量进行重新分层,而ISAP则会将\(level[x]\)重置为\(min{level[i]}+1\),其中\(i\)到\(x\)有一条有向边。
但仅仅有这个优化是不够的,ISAP的最大的优化来自GAP优化。
GAP优化就是看残余网络有无断层的情况(即其中任何一个节点都不属于某一层),若有的话直接退出即可。
ISAP的优化是非常明显的,在不开启O2优化的情况下,洛谷模板题最大数据只需约80ms,而上文的dinic需要约900ms。
下面附上代码:

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
const int maxm=2e5+10;
int flow[maxm],gap[maxn],dis[maxn],to[maxm],beg[maxm],nex[maxm];
int e=1,n,m,s,t;
void add(int x,int y,int z){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
flow[e]=z;
}
int isap(int x,int f){
if(x==t)return f;
int res=f,i;
for(i=beg[x];i;i=nex[i])
if(flow[i]>0 && dis[x]==dis[to[i]]+1){
int minflow=isap(to[i],min(res,flow[i]));
flow[i]-=minflow;
flow[i^1]+=minflow;
res-=minflow;
if(!res)return f;
}
if(!(--gap[dis[x]]))dis[s]=n;
gap[++dis[x]]++;
return f-res;
}
int main(){
int i,x,y,w;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,0);
}
int maxflow=0;
for(gap[0]=n;dis[s]<n;)maxflow+=isap(s,1e9);
printf("%d\n",maxflow);
return 0;
}

最小费用最大流

这类问题在最大流问题的基础上加上了一个费用的参数,要求在流量最大的基础上,费用最少。求出此时的流量与费用。

EK朴素算法

在EK增广路算法的基础上,使用spfa寻找费用最少的路径,其余基本与EK算法相同。
下面同样直接附上代码:

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<stdio.h>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e4+10;
const int INF=1e+9;
int to[maxn],nex[maxn],beg[maxn],c[maxn],w[maxn],pre[maxn],dis[maxn],vis[maxn],q[maxn<<3];
int n,e=1,m,s,t,maxflow;
inline int read(){
int flag=1,x=0;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return flag*x;
}
void add(register int x,register int y,register int flow,register int cost){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
c[e]=flow;
w[e]=cost;
}
int Spfa(){
for(register int i=1;i<=n;i++)dis[i]=INF;
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
int f=0,l=1;
q[1]=s;dis[s]=0;vis[s]=1;pre[s]=s;
while(f<l){
f++;
int k=q[f];
vis[k]=0;
for(register int i=beg[k];i;i=nex[i]){
int tmp=to[i];
if(c[i] && dis[tmp]>dis[k]+w[i]){
pre[tmp]=i;
dis[tmp]=dis[k]+w[i];
if(!vis[tmp]){
vis[tmp]=1;
q[++l]=tmp;
}
}
}
}
return !(dis[t]==INF);
}
int MCMF(){
int cost=0;
while(Spfa()){
int d=INF;
for(register int i=t;i!=s;i=to[pre[i]^1])
d=min(d,c[pre[i]]);
for(register int i=t;i!=s;i=to[pre[i]^1]){
c[pre[i]]-=d;
c[pre[i]^1]+=d;
cost+=w[pre[i]]*d;
}
maxflow+=d;
}
return cost;
}
int main(){
int x,y,flow,cost;
n=read();m=read();s=read();t=read();
for(register int i=1;i<=m;i++){
x=read();y=read();flow=read();cost=read();
add(x,y,flow,cost);
add(y,x,0,-cost);
}
int mincost=MCMF();
printf("%d %d\n",maxflow,mincost);
return 0;
}

zkw费用流

主体思路有点像dinic+spfa。类似于dinic的分层算法,zkw费用流先按照费用对图进行bfs分层,然后dfs搜索增广路,只有满足\(dis[i]+cost[i][j]=dis[j]\)才允许走这条增广路,直到无法搜索增广路,便再次对图分层,一直重复以上步骤直到无法搜出增广路。
效率上,洛谷的模板题,上文的EK算法运行时间大约是zkw费用流的两倍。
不过zkw费用流并非一直比EK要好。事实上,对于流量不大,费用不小,增广路还较长的网络,zkw体现出来的优势并不大,甚至可能比普通EK慢。

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
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int maxn=5e3+10;
const int maxm=5e4+10;
int to[maxm],nex[maxm],beg[maxm],flow[maxm],cost[maxm],dis[maxn],vis[maxn];
int n,mincost,e=1;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y,int f,int c){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
flow[e]=f;
cost[e]=c;
}
inline int bfs(int s,int t){
int i;
for(i=1;i<=n;i++)dis[i]=INF;
memset(vis,0,sizeof(vis));
vis[s]=1;
dis[s]=0;
deque<int> q;
q.push_back(s);
while(!q.empty()){
int x=q.front();q.pop_front();
for(i=beg[x];i;i=nex[i])
if(flow[i] && dis[x]+cost[i]<dis[to[i]]){
dis[to[i]]=dis[x]+cost[i];
if(!vis[to[i]]){
vis[to[i]]=1;
if(!q.empty() && dis[q.front()]>dis[to[i]])q.push_front(to[i]);
else q.push_back(to[i]);
}
}
vis[x]=0;
}
return (dis[t]==INF)?0:1;
}
inline int dfs(int x,int goal,int maxflow){
int i;
vis[x]=1;
if(x==goal)return maxflow;
for(i=beg[x];i;i=nex[i])
if(!vis[to[i]] && flow[i] && dis[x]+cost[i]==dis[to[i]]){
int tmp=dfs(to[i],goal,min(maxflow,flow[i]));
if(tmp>0){
flow[i]-=tmp;
flow[i^1]+=tmp;
mincost+=tmp*cost[i];
return tmp;
}
}
return 0;
}
inline int MCMF(int s,int t){
int maxflow=0;
while(bfs(s,t)){
vis[t]=1;
while(vis[t]){
memset(vis,0,sizeof(vis));
maxflow+=dfs(s,t,INF);
}
}
return maxflow;
}
int main(){
int i,m,s,t;
n=read();m=read();s=read();t=read();
int x,y,f,c;
for(i=1;i<=m;i++){
x=read();y=read();f=read();c=read();
add(x,y,f,c);
add(y,x,0,-c);
}
int maxflow=MCMF(s,t);
printf("%d %d\n",maxflow,mincost);
return 0;
}