网络流—Edmonds-Karp最短增广路算法(最大流)

思路

■ 求最大流的过程，就是不断找到一条源到汇的路径，然后构建残余网络，再在残余网络上寻找新的路径，使总流量增加，然后形成新的残余网络，再寻找新路径…..直到某个残余网络上找不到从源到汇的路径为止，最大流就算出来了。

■ 每次寻找新流量并构造新残余网络的过程，就叫做寻找流量的“增广路径”，也叫“增广”

现在假设每条边的容量都是整数，这个算法每次都能将流至少增加1

由于整个网络的流量最多不超过图中所有的边的容量和C，从而算法会结束

复杂度

找增广路径的算法可以用dfs，复杂度为边数m+顶点数n ，Dfs 最多运行C次，所以时间复杂度为 $C \times (m+n) =C \times n^2$
这个算法实现很简单
但是注意到在图中C可能会非常大

因此在每次增广的时候，选择从源到汇的具有最少边数的增广路径,即不是通过dfs寻找增广路径，而是通过bfs寻找增广路径。

这就是Edmonds-Karp 最短增广路算法

已经证明这种算法的复杂度上限为 $nm^2$ (n是点数，m是边数）

例题： Drainage Ditches

[ POJ - 1273 ]

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

Sample Output

赤裸裸的网络流题目。给定点数，边数，每条边的容量，以及源点，汇点，求最大流。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int G[300][300];
int Prev[300]; //路径上每个节点的前驱节点
bool Visited[300];
int n, m; //m是顶点数目，顶点编号从1开始 1是源，m是汇, n是边数

unsigned Augment(void)
{
    int v;
    int i;
    deque<int> q;
    memset(Prev, 0, sizeof(Prev));
    memset(Visited, 0, sizeof(Visited));
    Prev[1] = 0;
    Visited[1] = 1;
    q.push_back(1);
    bool bFindPath = false;

    //用bfs寻找一条源到汇的可行路径
    while (!q.empty()){
        v = q.front();
        q.pop_front();
        for (i = 1; i <= m; i++){
            if (G[v][i] > 0 && Visited[i] == 0){
                //必须是依然有容量的边，才可以走
                Prev[i] = v;
                Visited[i] = 1;
                if (i == m){
                    bFindPath = true;
                    q.clear();
                    break;
                }else
                    q.push_back(i);
            }
        }
    }

    if (!bFindPath)
        return 0;
    int nMinFlow = 999999999;
    v = m;
    //寻找源到汇路径上容量最小的边，其容量就是此次增加的总流量
    while (Prev[v]){
        nMinFlow = min(nMinFlow, G[Prev[v]][v]);
        v = Prev[v];
    }
    //沿此路径添加反向边，同时修改路径上每条边的容量
    v = m;
    while (Prev[v]){
        G[Prev[v]][v] -= nMinFlow;
        G[v][Prev[v]] += nMinFlow;
        v = Prev[v];
    }
    return nMinFlow;
}

int main(void)
{
    while (~scanf("%d%d", &n, &m)){
        //m是顶点数目，顶点编号从1开始
        int i, j, k;
        int s, e, c;
        memset(G, 0, sizeof(G));
        for (i = 0; i < n; i++){
            scanf("%d%d%d", &s, &e, &c);
            G[s][e] += c; //两点之间可能有多条边
        }

        unsigned int MaxFlow = 0;
        unsigned int aug;

        while (aug = Augment())
            MaxFlow += aug;
        cout << MaxFlow << endl;
    }
    return 0;
}