Edmonds-Karp算法

简单介绍一下,\(\text{EK}\)是每次找到一条经过的边数最少的增广路进行流量增广的算法.在每轮寻找增广路的过程中，\(\text{EK}\)算法只考虑图中\(f(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\)的最短路长度,则:

证明:

假设\(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),则\(\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,则有:

证明:

假设\(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,且\(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 
#include 
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