C++最大流算法详解（从零开始掌握Ford-Fulkerson算法与网络流编程）

核心概念：残量网络与增广路径

要解决最大流问题，我们需要理解两个关键概念：

• 残量网络（Residual Network）：表示当前还能增加多少流量的“剩余能力”图。
• 增广路径（Augmenting Path）：在残量网络中从源点到汇点的一条路径，沿着这条路径可以增加流量。

Ford-Fulkerson 方法的基本思想就是：不断在残量网络中寻找增广路径，直到找不到为止。此时的总流量即为最大流。

C++ 实现步骤

我们将使用邻接表存储图，并用 DFS（深度优先搜索）来寻找增广路径。以下是完整的代码实现：

#include <iostream>#include <vector>#include <climits>#include <algorithm>using namespace std;const int MAXN = 100; // 最大节点数// 图的邻接表表示vector<int> graph[MAXN];// 容量矩阵 cap[u][v] 表示从 u 到 v 的容量int cap[MAXN][MAXN];// 访问标记bool visited[MAXN];// DFS 寻找增广路径int dfs(int u, int t, int flow) {    if (u == t) return flow;    visited[u] = true;        for (int v : graph[u]) {        if (!visited[v] && cap[u][v] > 0) {            int min_flow = min(flow, cap[u][v]);            int result = dfs(v, t, min_flow);            if (result > 0) {                // 更新残量网络                cap[u][v] -= result;                cap[v][u] += result; // 反向边                return result;            }        }    }    return 0;}// Ford-Fulkerson 最大流算法int maxFlow(int s, int t) {    int total_flow = 0;    while (true) {        fill(visited, visited + MAXN, false);        int flow = dfs(s, t, INT_MAX);        if (flow == 0) break;        total_flow += flow;    }    return total_flow;}int main() {    int n, m; // n: 节点数, m: 边数    cin >> n >> m;        int u, v, c;    for (int i = 0; i < m; ++i) {        cin >> u >> v >> c;        graph[u].push_back(v);        graph[v].push_back(u); // 添加反向边（用于残量网络）        cap[u][v] = c;         // 初始容量        // 注意：cap[v][u] 默认为 0    }        int source = 0, sink = n - 1; // 假设源点是0，汇点是n-1    cout << "最大流为: " << maxFlow(source, sink) << endl;        return 0;}

代码说明

• graph 是邻接表，记录每个节点的邻居。
• cap[u][v] 存储从 u 到 v 的剩余容量。
• 每次 DFS 找到一条增广路径后，更新正向边和反向边的容量（这是残量网络的关键！）。
• 当 DFS 找不到新路径时，算法结束，返回累计的最大流。

优化建议：Edmonds-Karp 算法

上述实现使用 DFS，最坏时间复杂度较高。实际应用中常改用 BFS（即 Edmonds-Karp 算法），可保证多项式时间复杂度 O(VE²)。但作为入门，Ford-Fulkerson 的 DFS 版本更直观易懂。

总结

通过本文，你已经掌握了如何用 C++ 实现 Ford-Fulkerson 最大流算法。这不仅是学习 图论算法实现 的重要一步，也为解决实际工程中的流量分配问题打下基础。记住，理解残量网络和反向边是掌握最大流问题的关键！

关键词回顾：C++最大流算法、Ford-Fulkerson算法、网络流编程、图论算法实现。