引例

给定一个赋权的有向连通图，其权重代表该边能够承载的最大流量，请求出从一个节点s出发的，能够发往另一个节点t的最大流量。

这个是“最大流问题”的基本模型：

最大流问题

我们可以很自然地想到，对于任意一条从s到t的路径，制约其最大流量的一定是路径中承载能力最差的边。
然后，我们又想到，我们需要某种方式来记录算法运行过程中由于增添或删除流量导致每一边剩余的可用流量的暂时改变。我们维护了一个新的图，这个图的每一条边的权重代表当前边还能够容纳的剩余量，这个图叫剩余图。
同时，每一条从s到t的带有流量的路径被称为增广路径或者增长通路.

一个朴素的想法

我们可以得出一个很直观的算法：通过广度优先遍历或Dijkstra算法枚举剩余图中任意一条从s到t的流量不为零的路径，维护它所经过的边的最小流量，将这个流量累加至结果，再修改剩余图即可。
这种算法明显可以得出一个解，但是这个解是基于“选择任意一条路径”而来的，想想都知道它不太会是最优解。
不是最优解的原因是某且情况下更好的增广路径被阻断。因此我们想到，是否可以通过某种方式撤销已经投入使用的边呢，答案是肯定的。我们可以允许向已经存在流量的边的反方向发回流量，也就是说，我们新的增广路径中可以有反方向的边。
这个看上去很难理解，但实际上就是：一个存在着流量n的边，就有着把n个单位的流量返送回去的能力。也就是说，每次我们对于边uv添加流量n时，我们在残余图中就要添加边vu的流量n。

Ford-Fulkerson算法

应用上述的算法思想，我们可以将这个问题的解决方案归纳如下：

1. 先由Dijkstra算法找到剩余图中从s到t的一条路径
2. 基于上述的增广路径修改结果和剩余图
3. 若过程1无法找到任何的路径，那么算法结束

代码

class Ford_Fulkerson {
private:
    vector<vector<int>> originGraph;
    vector<vector<int>> residualGraph;
    deque<int> path;
    bool FindPath(int start, int end);
public:
    explicit Ford_Fulkerson(const vector<vector<int>> &graph) 
        : originGraph(graph), residualGraph(graph) {}
    int getMaxFlow(int start, int end);
};

bool Ford_Fulkerson::FindPath(int start, int end) {
    path.clear();

    vector<int> parent(originGraph.size(), int(-1));
    vector<int> visited(originGraph.size(), int(0));
    queue<int> BFS;
    BFS.push(start);

    int nowQueueSize = 0;
    while (nowQueueSize = BFS.size()) {
        for (int i = 0; i < nowQueueSize; i++) {
            visited[BFS.front()] = 1;
            for (int j = 0; j < residualGraph[BFS.front()].size(); j++) {
                if (!visited[j] && residualGraph[BFS.front()][j] > 0) {
                    BFS.push(j);
                    parent[j] = BFS.front();
                }
            }
            BFS.pop();
        }
        if (visited[end]) break;
    }

    if (parent[end] == -1) return false;
    while (end != -1) {
        path.push_front(end);
        end = parent[end];
    }
    return true;
}

int Ford_Fulkerson::getMaxFlow(int start, int end) {
    int res = 0;
    while (FindPath(start, end)) {
        int temp = INT_MAX;
        for (int i = 0; i < path.size() - 1; i++) {
            temp = std::min(temp, residualGraph[path[i]][path[i + 1]]);
        }
        res += temp;
        for (int i = 0; i < path.size() - 1; i++) {
            residualGraph[path[i]][path[i + 1]] -= temp;
            residualGraph[path[i + 1]][path[i]] += temp;
        }
    }

    return res;
}

但是这个算法存在着一个性能上的问题：如果有某些增广路径的通量特别大，程序如果在循环时选择了低通量的边，就需要通过大量的循环来消除它们，就会导致算法的运行时间变得很长。

一个解决方案是：总是选择通量较大的边优先计算，而这个实现是简单的：在寻找路径的算法中加入贪心算法即可。