网络流之增广路算法

这部分内容在《算法竞赛入门经典》——刘汝佳里面讲的已经很详细了。但里面对于反向流量的作用是没有说明的。这里只说一下反向流量的作用。

反向流量能够让后面的流自我调整。

例如当前状态下

网络流之增广路算法

当前状态下如何寻找？

用a表示残量, cap表示容量，很明显，3-4这条路不是最优的.

此时BFS, 会得到 a[2] = 2, a[4] = 2, a[3] = 1 (提示：cap[4][3]-flow[4][3]=1), a[5]=1, a[6]=1, a[7]=1

更新流量得到

网络流之增广路算法

可以看到，通过方向流量，使得网络流自我调整到最优。

附上代码:

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 20;
const int INF = (1<<30);

int cap[maxn][maxn], flow[maxn][maxn];
int n;

int EdmondsKarp(int s, int t) {
    int p[maxn], a[maxn];
    queue<int> q;

    memset(flow, 0, sizeof(flow));
    int f = 0;

    while(true) {
        memset(a, 0, sizeof(a));

        a[s] = INF;

        q.push(s);

        while(!q.empty()) { //BFS 找增广路
            int u = q.front(); q.pop();

            for(int v=1; v<=n; v++) if(!a[v] && cap[u][v]>flow[u][v]){
                //找到新节点v
                p[v] = u; q.push(v);
                a[v] = min(a[u], cap[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];  //更新反向流量
        }

        f += a[t];  //更新从 s 流出的流量
    }

    return f;
}

网络流之增广路算法

相关推荐