Edmond_Karp算法

核心思想:通过bfs不断在网络中寻找最短的增广路,从而求得最大流.
时间复杂度O(VE^2)

算法模板:

int Edmond_Karp(int s,int t)
{
    int ans=0;
    memset(flow,0,sizeof(flow));
    while (1)
    {
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        a[s]=INF;
        q.push(s);
        while (!q.empty())
        {
            int u=q.front();
            q.pop();
            for (int v=1;v<=n;v++)
            if (!a[v] && map[u][v]>flow[u][v])
            {
                p[v]=u;
                q.push(v);
                a[v]=Min(a[u],map[u][v]-flow[u][v]);
            }
        }
        if (a[t]==0) break;
        for (int u=t;u!=s;u=p[u])
        {
            flow[p[u]][u]+=a[t];
            flow[u][p[u]]-=a[t];
        }
        ans+=a[t];
    }
    return ans;
}