Max Flow Min Cut Algorithm.

这些算法都是基于Ford-Fulkerson 方法，

这个方法基本上是这样的一个循环：

Cap = 0;
while find Augmenting Path != NIL
Cap += decrease capacity of the Augmenting path

return Cap;

就是循环的寻找Augmenting Path（增广路径）， 然后再在图上的边的Capacity（容量）上减去这个值， 这样一直找， 知道找不到增广路径位置。

首先是一个基于BFS（广度有限搜索）的算法， 名字叫做： Edwinds-Karp alg：

下面是一个C++实现：

#include <vector>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <cstring>

using namespace std;

vector< vector<int> > matrix;
vector< vector<int> > capacity;

int bfs(int source, int size,  int sink) {
    queue<int> q;
    q.push(source);
    int from[size];
    bool visited[size];

    memset(from, -1, sizeof(from));
    memset(visited, false, sizeof(visited));

    visited[source] = true;
    // use bfs find the route to the sink.
    while(!q.empty()) {
        bool found_sink = false;
        int where = q.front();
        q.pop();

        // for each vertex next adjancent to where.
        for (auto next = matrix[where].begin(); next != matrix[where].end(); next++) {
            int val = *next;
            if (visited[val] == true)
                continue;
            if (capacity[where][val] > 0) {
                q.push(val);
                visited[val] = true;
                from[val] = where;
                if (val == sink) {
                    found_sink = true;
                    break;
                }
            }
        }
        if (found_sink)
            break;
    }

    //  then compute the path capacity.
    // Find the critical path from the sink back to source.
    // find the minimal path capacity of the path.
    int where = sink, prev, path_cap = INT_MAX;
    while (from[where] > -1) {
        prev = from[where];
        path_cap = min(path_cap, capacity[prev][where]);
        where = prev;
    }

    // then update the residual network, if no path is found the while loop will not be enter.

    // Then - augment.
    where = sink;
    while (from[where] > -1) {
        prev = from[where];
        capacity[prev][where] -= path_cap;
        capacity[where][prev] += path_cap;
        where = prev;
    }

    // if no path is found, path_cap is infinity.
    // and return the augmenting capacity.
    if (path_cap == INT_MAX)
        return 0;
    else
        return path_cap;
}

int max_flow()
{
    int result = 0, path_cap ;
    while (true) {
        path_cap = bfs(1, 8, 7);
        if (path_cap == 0)
            break;
        else
            result += path_cap;
    }
    return result;
}

这个实现的是基于BFS的。

BFS 里面的循环基本就是一个标准的BFS遍历方法， 检测条件的时候增加了一个路径的Capacity（容量）必须大于0, 这样就不会找到已经满了路径了。顺着source一直走到sink以后， 记录下路径。

然后通过sink反着找到Capacity最小的一条边， 记录这个值。

最后在路径上对于正方向， 减去这个指， 对于反方向， 增加这个值。并且返回这个数值。

这个实现的算法复杂度是O(VE²）， 因为BFS的负责读是O(E)， 而其他每一次找增广路径的计算的复杂度是O(V）。