Edmonds-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的最短路长度,则:

证明:

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

证明:

假设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:

若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;
}