网络流

Posted by XTXTMTXTX on 2019-03-06
#Algorithm #C++ #OI
OI
字数：1.6k
阅读时间：7 分钟
本文总阅读量 次

  一直以来都觉得网络流特别的高深莫测，所以就没有怎么用心看过。结果在学校校队选拔赛碰上了道网络流套路题，当场就跳过了。事后想想不行，不管怎么样的算法总得先去学才能会，于是看了几篇博客，姑且是按着博客里的介绍自己一行行打出来了。当然了，这里并不做什么再次讲解，纯粹丢个有注释的代码就跑了（方便以后忘了回来看眼）。对于网络流具体应该怎么理解，可以看这篇博客：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 就是答案。


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