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

网络流前置概念

网络

 网络是指一个有向图$G=(V,E)$，这个有向图有两个特殊节点：源点$S$和汇点$T$。每条有向边$(x,y)\in E$有一个权值$c(x,y)$，称为边的容量。若$(x,y)\notin E$。则$c(x,y)=0$。

 我们用$f(x,y)$表示$(x,y)$上的流量，$c(x,y)-f(x,y)$为边的剩余容量。通常用$f(x,y)/c(x,y)$表示边上的流量与容量。

可行流

 若一个流对每一发点满足总流出量与总流入量之差不大于提供能力，对每一收点满足总流入量与总流出量之差不小于接收能力，则称这个流为可行流。

 对于一个可行流，必须满足一下条件：
 1.容量限制：每条边的流量不能超过每条边容量。
 2.流量守恒：除源点与汇点外，进入的流量等于流出的流量。

最大流 增广路 残留网：

最大流：从源点流向汇点的最大流量

增广路：一条从源点到汇点的所有边剩余容量$\ge 0$的路径

残留网：由网络中的所有结点和剩余容量$>0$的边构成的子图，这里的边包括有向边和其反向边。

网络最大流

 实际上，找最大流的过程就是不断从源点到汇点找增广路的过程。

 我们在建图时对每条有向边$(x,y)$都构建一条反向边$(y,x)$，初始容量$c(y,x)=0$。构建反向边的目的是为了提供一个“退流管道”，一旦前面的增广路堵死可行流，可以通过“退流管道”退流，提供了“后悔机制”。如下图所示：（图中红色的边就是退流管道）



 我们可以发现，退流管道的容量和原方向边的容量的和等于最初始的边的容量。有了退流管道的帮助，我们就不必担心增广路堵死可行流的情况，就能找出网络最大流了。

具体说明：

1.$bfs$找增广路：
 我们需要一个pre数组来存储当前到的点的前驱边。（方便EK逆序更新残留网）。
2.$EK()$找最大值：
 (1).逆序更新残留网，容量“此消彼长”。
 (2).累加可行流，然后返回最大值。

代码实现：

#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 mf[N],pre[N];
int n,m,S,T;

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(mf,0,sizeof mf);
	queue<int>q;
	q.push(S),mf[S]=inf;
	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(!mf[v] and e[i].c){
				pre[v]=i;
				mf[v]=min(mf[u],e[i].c);
				q.push(v);
				if(v==T)return true;
			}
		}
	}
	return false;
}

inline int EK(){
	int flow=0;
	while(bfs()){
		int v=T;
		while(v!=S){
			int i=pre[v];
			e[i].c-=mf[T];
			e[i^1].c+=mf[T];
			v=e[i^1].v;
		}
		flow+=mf[T];
	}
	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<<EK()<<'\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

 我们来浅浅地估计一下$EK$算法的复杂度，每一次找增广路最多为$m$，最多需要找$n$次，总复杂度是$O(n{m}^2)$的，但实际上复杂度并没有那么高，在面对有些较大的数据时任然不会$T$的。