网络流

Posted by XTXTMTXTX on 2019-03-06
OI


  一直以来都觉得网络流特别的高深莫测,所以就没有怎么用心看过。结果在学校校队选拔赛碰上了道网络流套路题,当场就跳过了。事后想想不行,不管怎么样的算法总得先去学才能会,于是看了几篇博客,姑且是按着博客里的介绍自己一行行打出来了。当然了,这里并不做什么再次讲解,纯粹丢个有注释的代码就跑了(方便以后忘了回来看眼)。对于网络流具体应该怎么理解,可以看这篇博客:https://blog.csdn.net/lzoi_hmh/article/details/74940366
  首先,这是我按照网络流想法直接实现的一个非常朴素、低效的代码,见下:

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 205
#define MAXM 205
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
inline int read(){//读写优化
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int lines=0,First[MAXN],Next[MAXM*2],w[MAXM*2],v[MAXM*2];
bool visited[MAXN];
inline void addline(int x,int y,int z){//链式前向星加边
Next[lines]=First[x];
First[x]=lines;
v[lines]=y;
w[lines]=z;
lines++;
}
int n,m,stuck[MAXN],stop=0,ans=0;//stuck存放增广路上经过的边
bool dfs(int x){
if(x==n){
int d=w[stuck[0]];
for(int i=1;i<stop;i++)d=min(d,w[stuck[i]]);//遍历增广路上的边找出最大能通过的流量
for(int i=0;i<stop;i++){
w[stuck[i]]-=d;//遍历增广路上的边并减去相应流量
w[stuck[i]^1]+=d;//遍历增广路上的边并为其反向边加上相应流量
}
ans+=d;
stop=0;
memset(visited,0,sizeof(visited));//清理数组,准备下一次增广
return 1;
}
for(int i=First[x];i!=-1;i=Next[i]){//遍历该点引出的边
if(!w[i]||visited[v[i]])continue;//当前边无剩余流量,跳过
stuck[stop++]=i;//将该边压栈
visited[v[i]]=1;//防止走回路
if(dfs(v[i]))return 1;//如果下一层dfs找到增广路,直接返回true
visited[v[i]]=0;//回溯
stop--;//出栈
}
return 0;//未找到增广路,返回false
}
int main(){
m=read(),n=read();
memset(First,-1,sizeof(First));//初始化
for(int i=0;i<m;i++){
int x=read(),y=read(),z=read();
addline(x,y,z);//添加当前边
addline(y,x,0);//添加反向边
//一条边的反向边编号即为该边编号^1,e.g.,123号边反向边为123^1==122
}
visited[1]=1;
while(dfs(1));//不断重复dfs直到无法增广
printf("%d\n",ans);//输出答案
return 0;
}

  每次 dfs 都只增广一条增广路,找到汇点就直接退出,提交到 Codevs 1993 上,不出意外地 TLE 了。
  对其稍加改进,增加分层、一次增广多条路径,也就是 dinic 算法,于是写成了这样:

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 205
#define MAXM 205
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
inline int read(){//读写优化
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int lines=0,First[MAXN],Next[MAXM*2],w[MAXM*2],v[MAXM*2],dis[MAXN];
inline void addline(int x,int y,int z){//链式前向星加边
Next[lines]=First[x];
First[x]=lines;
v[lines]=y;
w[lines]=z;
lines++;
}
int n,m,ans=0,st,ed;
inline bool bfs(){//DINIC分层,即BFS搜索每个点到源点最短距离
static int h,t,que[MAXN];
static bool b[MAXN];//判断是否遍历到过
memset(b,0,sizeof(b));
memset(dis,-1,sizeof(dis));
h=0,t=1;
que[h]=st;
b[st]=1;
dis[st]=0;
while(h!=t){
int x=que[h++];h%=MAXN;
for(int i=First[x];i!=-1;i=Next[i]){
if(b[v[i]]||!w[i])continue;//跳过已访问过的点及不流通的点
dis[v[i]]=dis[x]+1;
que[t++]=v[i];t%=MAXN;
b[v[i]]=1;
}
}
return b[ed];//返回汇点能否遍历到
}
int dfs(int x,int flow){//x表示当前点,flow表示到该点的流量,源点正无穷设为-1,并返回该点流到汇点的流量
if(x==ed)return flow;//找到汇点,返回流量
int c,d=0;
for(int i=First[x];i!=-1;i=Next[i]){
if(!w[i]||dis[v[i]]!=dis[x]+1)continue;//跳过非下一层的点及不流通的点
c=dfs(v[i],((flow==-1||w[i]<(flow-d))?w[i]:(flow-d)));//传入下一层DFS,可用流量为该边剩余流量或该点剩余流量
d+=c;//该点流出流量
w[i]-=c;//该边减去相应剩余流量
w[i^1]+=c;//该边反向边加上相应剩余流量
}
return d;//返回该点最终流出流量
}
int main(){
n=read();m=read();
st=read();ed=read();
memset(First,-1,sizeof(First));//初始化
lines=0;ans=0;
for(int i=0;i<m;i++){
int x=read(),y=read(),z=read();
addline(x,y,z);//添加当前边
addline(y,x,0);//添加反向边
//一条边的反向边编号即为该边编号^1,e.g.,123号边反向边为123^1==122
}
while(bfs())ans+=dfs(st,-1);//直到源点到汇点无通路,不断增广
printf("%d\n",ans);//输出答案
return 0;
}

  其实可以发现,大部分讲网络流的文章里都提到了增加反向弧、剩余流量、最大流量的概念。一开始我也是因为这些概念多,下意识认为实现起来特别麻烦就放弃了。其实利用链式前向星的存图方法的话,只要在加单向边的时候增加一条相反的、剩余流量为 0 的边,然后当作普通的边处理就可以了;互相找反向边也很方便,直接异或 1 就可以了。至于最大流量和剩余流量,只要确保正向边和反向边剩余流量都不为负即可,不用管最大流量。另外无向图建图时,给反向边也设置成与正向边相同的剩余流量就可以了。
  另外最大流与最小割是可以互相转换的,但如果要知道最小割的边数就会显得有点麻烦。其实有一个办法,在 m * sigma ( ci ) 不会爆精度的情况下,可以在加边时让每条边的流量存为 ci * m + 1,最终 ans % m 就是最小割的边数,ans / m 就是答案。


当你在凝视深渊的时候 深渊也正在凝视着你