图论——最大流的增广路相关算法（基于Ford–Fulkerson方法的DFS和BFS、Dinic算法）_fordfulkerson dfs bfs

最小割定理

割($CUT$)，指对于某个顶点集合$S$包含于集合$V$，从$S$出发指向$T$的那些边的集合，记为$CUT(S,T)$，这些边的容量之和称为割的容量。设$s$属于集合$S$，$t$属于集合$V-S$，如果将网络中$s$-$t$割所包含的边都删去，就不存在$s$指向$t$的路径了。

$f$为流，$CUT(s,t)$为任意的割，$f$的值为所有正向割边的流量与负向割边的差。因为有$f$的流量等于$s$出边的总流量，对于任意的非$s$点$v$，$v$的出边总流量等于它的入边总流量，所以$f$的流量等于出$s$所有结点的出边总流量减入边总流量。由此可知，如果$f$是网络中的一个流，$CUT(s,t)$是一个割，那么f的值不超过割$CUT(s,t)$的容量。网络中的最大流不超过任何割的容量。

在网络中，如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流， CUT(S,T)是一个最小割。

增广路相关算法的目的就是使得源点到汇点的割所包含的边全部删去。当源点到汇点无路可走时，则$f$到达最大值。

基于Ford–Fulkerson方法的DFS

Ford-Fulkerson方法的一种实现是利用DFS寻找增广路径和删去 “ 割集中的边 ”。每次找到一条从源点到汇点的路径，记录这条路径的流的最大值即为路径上权值最小的边。并建立反边表示 “ 删去” 正向边，以便于在后来调整路径。当没有通向汇点的路径时，流饱和，退出搜索。由于每次DFS至少找到一条流$f=1$的路径，并且最多遍历所有边，所以该算法的复杂度$O(f|E|)$，不过这种最差的情况一般是不会出现的，总体上说该算法还是比较快的。（除非出题者坑你）

为了便于理解，我用一些图表现这一算法的思路。
设$c$为路的容量，$r$为反向边的容量，$f$为占用的流。
建立一张图，假设此时求点1到点5的最大流。

用c++实现的代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int inf=0x7fffffff;
struct EDGE{
	int v;//通往结点 
	int c;//路径容量 
	int rev;//反向连接点 
};
vector<EDGE> edge[101];
bool vis[101];//DFS时记录结点的访问情况 
int n;//n个结点 
int m;//m条边；
int s;//源点 
int t;//汇点
int flow;//最大流;

int dfs(int u,int f)
{
	if(u==t) return f;
	vis[u]=true;
	for(int i=0;i<edge[u].size();++i)
	{
		EDGE &e=edge[u][i];
		if( !vis[e.v] && e.c>0 )
		{
			int d=dfs(e.v,min(f,e.c));//不断更新这条路径上最小的流
			if(d>0)
			{
				e.c-=d;
				edge[e.v][e.rev].c+=d;//找到流f之后，回溯更新反边的流
				return d; 
			} 
		}
	}
	return 0;
} 
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;++i)
	{
		int u,v,cap;
		cin>>u>>v>>cap;
		EDGE in;
		in.v=v,in.c=cap,in.rev=edge[v].size();
		edge[u].push_back(in);
		in.v=u,in.c=0,in.rev=edge[u].size()-1;
		edge[v].push_back(in);//为建立方向边做准备; 
	}
	while(1)//不断循环增广路径并累加流 
	{
		memset(vis,0,sizeof(vis));
		int f=dfs(s,inf);
		if(!f) break;
		flow+=f;
//		cout<<flow<<endl;
	}
	
	cout<<flow<<endl;
	return 0; 
}
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

Ford-Fulkerson方法的BFS实现：Edmond-Karp算法

Edmond-Karp是FF方法的BFS实现方式，其稳定性高于上面用DFS找增广路的方法，不会因为最大流的限制而出现爆炸性的时间消耗，其时间复杂度为$O(V{E}^2)$。

思想同Ford-Fulkerson方法，代码已经注释；

#include<iostream>
#include<queue>
#include<vector>
#include<cstring> 
using namespace std;

const int inf=0x7fffffff;
int edge[101][101];//邻接矩阵存边的权值，附带建立反边 
queue<int> q;//bfs常规操作  
int flow[101];//记录增广路径上的最小流 
int pre[101];//记录增广路径上每个点的前驱，并且判断是否连通到汇点 
int n;//结点数 
int m;//边数 
int st;//源点 
int ed;//汇点 

int bfs()//bfs搜索增广路径 
{
	for(int i=1;i<=n;++i)//初始化每个点的前驱为-1 
		pre[i]=-1;
	while(!q.empty()) q.pop();//清空队列 
	pre[st]=0;
	flow[st]=inf;
	q.push(st);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(u==ed) break;
		for(int i=1;i<=n;++i) 
		{
			if(i!=st&&edge[u][i]>0&&pre[i]==-1)//寻找能够增广的结点 
			{
				pre[i]=u;//记录前驱 
				flow[i]=min(flow[u],edge[u][i]);//迭代出合适的流的大小 
				q.push(i);
			}
		}
	}
	if(pre[ed]==-1) return -1;//判断是否连通到汇点 
	return flow[ed];
}
int Edmond_Karp()
{
	int addflow=0;
	int sumflow=0;
	while(addflow=bfs()!=-1)//寻找增广路径，当无增广路径时结束循环 
	{
		int node=ed;
		while(node!=st)//通过查看前驱，找到增广路径上的每一条边和点，并减少边的容量和建立反边 
		{
			int last=pre[node];
			edge[node][last]+=addflow;
			edge[last][node]-=addflow;
			node=last;
		}
		sumflow+=addflow;
	}
	return sumflow;
}
int main()
{
	cin>>n>>m>>st>>ed;
	for(int i=1;i<=m;++i)
	{
		int fr,to,cap;
		cin>>fr>>to>>cap;
		edge[fr][to]+=cap;
	}
	
	cout<<Edmond_Karp()<<endl;;
	
	return 0;
 } 
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

Dinic算法、弧优化

算法原理
DInic算法是对Edmond-Karp算法的一种优化，它总是寻找最短的增广路径(通过结点数少)，并沿着这条路径更新流。最短增广路径的长度在增广过程中始终不会变短，所以无需每次找增广路前都进行一次bfs。可以先进行一次bfs，按各个点被发现的顺序建立分层图，然后我们在进行dfs找到最短的增广路径，即增广的方向就是先被发现点指向后被发现的点。当没有新的最短增广路径时，意味着需要扩大最短增广路径的长度。此时再进行一次bfs，顺便可以检测是否还有通向汇点的路径。每一次bfs建立分层图的时间复杂度都是$O(E)$，每一步最短增广路径的长度至少增加$1$，最多增加到$|V|-1$。时间复杂度最坏为$O(|E||V{|}^2)$.实际操作中很难出现能卡死该算法的反人类图。

弧优化
我们用邻接表建图，对于一次bfs预处理下的dfs搜索最短增广路操作，实际上是重复利用残余图。但是没有必要对一个结点已经搜索过的边重复搜索，因此用一个数组，记录此时应该从这个结点的第几条边开始遍历。

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int inf=0x7fffffff;
int n;//结点数 
int m;//边数 
int st;//源点 
int ed;//汇点 
struct EDGE{
	int v;//边指向的结点 
	int c;//边的权值 
	int rev;//反向边 
};
vector<EDGE> edge[101];
queue<int> q;
int level[101];//分层图各个结点的等级 
int iter[101];//弧优化 

void bfs()//一个普通的bfs，记录每个点被发现的顺序 
{
	for(int i=1;i<=n;++i)
		level[i]=-1;
	level[st]=0;
	q.push(st);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<edge[u].size();++i)
		{
			EDGE &e=edge[u][i];
			if(e.c>0&&level[e.v]==-1)
			{
				level[e.v]=level[u]+1;
				q.push(e.v);
			}
		}
	} 
}
int dfs(int u,int f)
{
	if(u==ed) return f;
	for(int &i=iter[u];i<edge[u].size();++i)//弧优化，标记结点u没有遍历的位置，避免重复搜索 
	{
		EDGE &e=edge[u][i];
		if(e.c>0&&level[e.v]>level[u])
		{
			int d=dfs(e.v,min(f,e.c));//迭代寻找这条路径流的大小。 
			if(d>0)
			{
				e.c-=d;
				edge[e.v][e.rev].c+=d;
				return d;
			} 
		}
	}
	return 0;
}
int Dinic()
{
	int sumflow=0;
	while(1)
	{
		bfs();//预处理，对图分层 
		if(level[ed]<0) break;//判断是否能连通汇点 
		memset(iter,0,sizeof(iter));//初始化弧 
		int addflow;
		while(1)//迭代找最短增广路 
		{
			addflow=dfs(st,inf);
			if(!addflow) break;
			sumflow+=addflow;
		}
	}
	return sumflow;
}
int main()
{
	cin>>n>>m>>st>>ed;
	for(int i=1;i<=m;++i)
	{
		int fr,to,cap;
		cin>>fr>>to>>cap;
		EDGE in;
		in.v=to,in.c=cap,in.rev=edge[to].size();
		edge[fr].push_back(in);
		in.v=fr,in.c=0;in.rev=edge[fr].size()-1;
		edge[to].push_back(in);
	}
	
	cout<<Dinic()<<endl;
	
	return 0;
 } 
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
92
93
94
95
96
97

后记

由于博主太菜了，本来是要弄几道例题做做的，奈何找到的例题都是神仙题。凭我的菜鸡水平完全看不出是网络流题。。。
所以没有例题了。。。