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

推荐上看下。

 

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

例如当前状态下

当前状态下如何寻找？

用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 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
           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;}