最大流算法

最大流问题是指在一个有向图中，每条边的容量有限，求两点间能通过的最大流量。解决此问题常用Ford–Fulkerson方法，本文对此方法做一总结记录。

在最大流问题中，涉及到很多术语，如残留网络、增广路径等，本文不打算使用和介绍这些名词，想深入了解此问题的话可进一步阅读文末的参考资料，这里仅从编程使用的角度介绍算法实现方法。

Ford–Fulkerson方法的基本步骤很简单：

1. 在当前的图中寻找任意一条从源点到汇点的路径；
2. 为这条路径添加一条反向路径；
3. 重复以上两步，直至无法找到更多的路径为止。

这个算法如此简单，很让人怀疑其正确性，不过，根据最大流与最小割定理，我们可以严格的证明：只要每一条边的容量都是有理数，Ford–Fulkerson方法肯定收敛于图的最大流，然而，若容量是无理数，算法不一定会收敛。证明步骤可以参考第二篇参考资料。

算法的执行过程可以参考这个动画演示。

此方法之所以称为Ford–Fulkerson方法而不是Ford–Fulkerson算法的原因在于，第一步寻找路径的过程可以使用很多不同的策略，这就可以衍生出各种不同的具体实现算法，其中最常用的一种是使用BFS广度优先搜索策略，这种算法称之为Edmonds-Karp算法。最后一篇参考资料中给出了一个实现代码，此处给出另一种封装更好一些的实现代码，实用邻接表实现。

---

图的相关数据结构定义：

typedef struct _path {
    int dst;
    int flow;
} path;

typedef struct _vertex {
    list<path> adjacency;	// 邻接表
    bool visited;			// BFS搜索记录
    int pre;				// 前一个节点
    int minflow;			// 当前路径流量
} vertex;

FindPath()函数使用BFS搜索src至dst之间的一条路径，并计算此条路径的流量：

bool FindPath(vector<vertex> & G, int src, int dst) {
    deque<int> buf;
    buf.push_back(src);

    while (!buf.empty()) {
        int s = buf.front();
        buf.pop_front();

        G[s].visited = true;
        if (s == dst)
            return true;

        // 更新与G[s]节点相连的所有节点的状态
        for (auto it = G[s].adjacency.begin(); it != G[s].adjacency.end(); it++) {
            // 未访问过且有剩余流量
            if (!G[it->dst].visited && it->flow > 0) {
                G[it->dst].pre = s;
                G[it->dst].minflow = it->flow < G[s].minflow ? it->flow : G[s].minflow;
                buf.push_back(it->dst);
            }
        }
    }
    return false;
}

AddFlow()函数更新流量信息（减去正向流量并添加反向流量），返回值即为当前路径流量：

int AddFlow(vector<vertex> & G, int src, int dst) {
    int v = dst;
    int minflow = G[v].minflow;
    while (v != src) {
        for (auto it = G[v].adjacency.begin(); it != G[v].adjacency.end(); it++) {
            if (it->dst == G[v].pre) {
                it->flow += minflow;
                break;
            }
        }
        for (auto it = G[G[v].pre].adjacency.begin(); it != G[G[v].pre].adjacency.end(); it++) {
            if (it->dst == v) {
                it->flow -= minflow;
                break;
            }
        }
        v = G[v].pre;
    }	
    return minflow;
}

GClear()函数用于清除上一次BFS的中间数据，为下一次循环做好准备：

void GClear(vector<vertex> & G) {
    for (auto it = G.begin(); it != G.end(); it++) {
        it->visited = false;
        it->minflow = INT_MAX;
        it->pre = -1;
    }
}

最后是测试用的main()函数：

int main() {
    int V,E;
    cout << "V, E : ";
    cin >> V >> E;
    vector<vertex> G = vector<vertex>(V);

    GClear(G);
    while (E--) {
        int s, d, f;
        cin >> s >> d >> f;
        G[s].adjacency.push_back((path){d, f});
        G[d].adjacency.push_back((path){s, 0});  // 反向流量初始值为0
    }

    int src, dst;
    cout << "src, dst: ";
    cin >> src >> dst;

    int flow = 0;
    while (FindPath(G,src,dst)) {
        flow += AddFlow(G, src, dst);
        GClear(G);
    }

    cout << "MaxFlow: " << flow << endl; 
    return 0;
}

---

参考资料：
算法导论（Introduction to Algorithm）第26章 最大流
6.854 高级算法 —— 网络流 最大流
最大流（一）