网络流——Dinic算法求最大流

 上一次我写了$EK$算法的博客，但是$EK$算法在实现的过程中有一点缺陷，就是它只能每一次累加一条增广路的流量。有没有一种算法可以同时累加多条增广路的流量？于是，$Dinic$算法就诞生了。

Dinic算法主要流程：

1.bfs对点分层，找增广路
2.dfs多路增广(入下回离)
 (1).搜索顺序优化（分层限制搜索深度）
 (2).当前弧优化（剪枝）
 (3).剩余流量优化（剪枝）
 (4).残枝优化（价值）（踢出图层）
3.dinic累加可行流

PS：关于为什么分层的一个理解：
如果不分层，可能会出现以下情况：

 如果程序选择了1、2、3、4这条路径增广，但是我们可以自己模拟一遍后发现这样的效率特别低。（尤其在最大容量越大时更为突出）但我们如果对原图进行分层，就不会出现这种情况了。

Dinic算法代码实现：

#include
#define in read()
#define cs const
#define re register
#define int long long
using namespace std;

cs int N=205;
cs int M=5050<<1;
cs int inf=1e9;

struct edge{
	int v,c,ne;
}e[M];
int h[N],tot=1;

int n,m,S,T;
int cur[N],dep[N];

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

inline void add(int a,int b,int c){
	e[++tot]=(edge){b,c,h[a]};
	h[a]=tot;
}

inline bool bfs(){
	memset(dep,0,sizeof dep);
	queue<int>q;
	q.push(S),dep[S]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(re int i=h[u];i;i=e[i].ne){
			int v=e[i].v;
			if(!dep[v] and e[i].c){
				dep[v]=dep[u]+1;
				q.push(v);
				if(v==T)return true; 
			}
		}
	}
	return false;
}

int dfs(int u,int mf){
	if(u==T)return mf;
	int sum=0;
	for(re int i=cur[u];i;i=e[i].ne){
		int v=e[i].v;
		if(dep[v]==dep[u]+1 and e[i].c){
			int f=dfs(v,min(mf,e[i].c));
			e[i].c-=f;
			e[i^1].c+=f;
			sum+=f;
			mf-=f;//减少u的剩余流量 
			if(!mf)break;//余量优化 
		}
	}
	if(!sum)dep[u]=0;//残枝优化 
	return sum;
}

int dinic(){
	int flow=0;
	while(bfs()){
		memcpy(cur,h,sizeof cur);
		flow+=dfs(S,inf); 
	}
	return flow;
}

signed main(){
	n=in,m=in,S=in,T=in;
	for(re int i=1;i<=m;i++){
		int u=in,v=in,c=in;
		add(u,v,c),add(v,u,0);
	}
	cout<<dinic()<<'\n';
	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

 再来估计一下时间复杂度，每一次$bfs$的复杂度是$O(n)$的，每个点在$dfs$中都可能调用所以是$O(n)$的，$dfs$的多路增广最多是$O(m)$的，总复杂度是$O(m{n}^2)$的。