Edmunds-Karp算法

简单介绍一下,$\text{EK}$是每次找到一条经过的边数最少的增广路进行流量增广的算法.在每轮寻找增广路的过程中，$\text{EK}$算法只考虑图中$f(u, v)<c(u, v)$的边，任意一条能从$s$通到$t$的路径都是一条增广路。根据斜对称性，反边都是可以走的。记录下该路径上的最小残量和前驱，到达$t$时可以退出$\text{BFS}$，然后从$t$回溯到$s$更新经过的边的容量。时间复杂度：$O(nm^2)$，一般能处理$10^3$~$10^4$规模的网络。

下面证明一下$\text{EK}$的复杂度(可以跳过直接看下方代码).

引理1:

设$f_i$为增广$i$次之后的容许流(即已经选择流过的合法网络),$\lambda^k(u,v)$表示$f_k$中$u$到$v$的最短路长度,则:

$\lambda^k(S,v)\le \lambda^{k+1}(S,v),\lambda^k(v,T)\le\lambda^{k+1}(v,T)$

证明:

假设$f_{k+1}$中一条从$S$到$v$的最短路为$S\rightarrow u_1,\cdots,\rightarrow u_{x-1}\rightarrow u_x,u_x=v,\lambda^{k+1}(S,v)=x$.
记$e_i=(u_{i-1},u_i)$.
若$e_i$在$f_k$中同样可用,即$f(u_{i-1}, u_i)<c(u_{i-1}, u_i)$,则$\lambda^k(S,u_i)\le \lambda^k(S,u_{i-1})+1$;
若$e_i$在$f_k$中不可用,则$e_i'$($e_i$的反向边)必然可用.而且因为$e_i$在$f_k$中不可用,在$f_{k+1}$中变成可用,说明$e_i'$在$f_k$中被进行了增广使得$e_i$可用.也就说明了$e_i'$在$S$到$v$的最短路上,即$\lambda^k(S,u_{i-1})= \lambda^k(S,u_{i})+1$,也满足上面的不等式.
综上所述,$\lambda^k(S,v)=\lambda^k(S,u_x)\le x=\lambda^{k+1}(S,v)$

引理2:

设边$e$在$f_k$变为$f_{k+1}$的增广路中,$e'$在$f_j$变成$f_{j+1}$的增广路中$(k<j)$,则有:

$\lambda^{j}(S,T)\ge \lambda^{k}(S,T)+2$

证明:

假设$e=(u,v)$,则:$\lambda^{k}(S,v)=\lambda^{k}(S,u)+1,\lambda^{j}(S,T)=\lambda^{j}(S,v)+1+\lambda^{j}(u,T)$
由引理1:
$\lambda^{j}(S,T)\ge \lambda^{k}(S,v)+1+\lambda^{k}(u,T)=\lambda^{k}(S,u)+\lambda^{k}(u,T)+2=\lambda^{k}(S,T)+2$

若$e$在$k_1,k_2,\cdots,k_x$中在最短增广路上,则必有$j_1,j_2\cdots$使得$k_1<j_1<k_2<j_2<\cdots$,且$e'$在$j_1,j_2\cdots$中在最短增广路上.因为$1\le \lambda^{k_1}(S,T),\lambda^{k_x}\le n$,所以$x\le\frac{n+2}{4}$.即每条边最多被增广$\frac{n+2}{4}$次,而每次增广的复杂度是$O(m)$的,总的复杂度即为$O(\frac{n+2}{4}*m*m)=O(m^2n)$.
证毕.

代码：

#include <cstdio>
#include <cstring>
const int maxn=10000+10;
const int maxm=100000+10;
const int INF=0x3f3f3f3f;
int head[maxn],to[maxm<<1],nxt[maxm<<1],val[maxm<<1];
int tot=1,maxflow=0;
int pre[maxn],minf[maxn];
int n,m,s,t;
struct Queue
{
	int a[maxn];
	int l,r;
	Queue() {l=1,r=0;}
	void push(int x) {a[++r]=x;}
	void pop() {l++;}
	int front() {return a[l];}
	bool empty() {return l>r;}
}q;

int min(int x,int y) {return x<y?x:y;} 
void add(int u,int v,int w)
{
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=w;
}
bool bfs()
{
	memset(pre, 0, sizeof(pre));
	pre[s]=-1;
	minf[s]=INF;
	q=Queue();
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if (pre[v]||!val[i])
				continue;
			pre[v]=i;
			minf[v]=min(minf[u], val[i]);
			q.push(v);
			if (v==t)
				return 1;
		}
	}
	return 0;
}
void update()
{
	int u=t,d=minf[t];
	while(u!=s)
	{
		int i=pre[u];
		val[i]-=d;
		val[i^1]+=d;
		u=to[i^1];
	}
	maxflow+=d; 
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (int i=1;i<=m;i++) 
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u, v, w),add(v, u, 0);
	}
	while(bfs())
		update();
	printf("%d\n",maxflow);
	return 0;
}