深入理解C++最大流算法（从零开始掌握网络流核心思想与实现）

核心概念

• 源点（Source）：流量的起点，通常记为 S。
• 汇点（Sink）：流量的终点，通常记为 T。
• 容量（Capacity）：每条边能承载的最大流量。
• 残量网络（Residual Network）：用于寻找增广路径的关键结构。

算法一：Edmonds-Karp 算法

Edmonds-Karp算法是 Ford-Fulkerson 方法的一种具体实现，它使用 BFS（广度优先搜索）来寻找增广路径，保证了时间复杂度为 O(V·E²)，其中 V 是顶点数，E 是边数。

其核心思想是：不断在残量网络中找从源点到汇点的最短路径（按边数），并沿该路径增加流量，直到无法再找到增广路径为止。

C++ 实现代码

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;const int MAXN = 1005;int capacity[MAXN][MAXN];int parent[MAXN];bool visited[MAXN];bool bfs(int s, int t, int n) {    fill(visited, visited + n, false);    queue<int> q;    q.push(s);    visited[s] = true;    parent[s] = -1;    while (!q.empty()) {        int u = q.front();        q.pop();        for (int v = 0; v < n; v++) {            if (!visited[v] && capacity[u][v] > 0) {                q.push(v);                parent[v] = u;                visited[v] = true;            }        }    }    return visited[t];}int edmondsKarp(int s, int t, int n) {    int max_flow = 0;    while (bfs(s, t, n)) {        int path_flow = INT_MAX;        for (int v = t; v != s; v = parent[v]) {            int u = parent[v];            path_flow = min(path_flow, capacity[u][v]);        }        for (int v = t; v != s; v = parent[v]) {            int u = parent[v];            capacity[u][v] -= path_flow;            capacity[v][u] += path_flow;  // 反向边        }        max_flow += path_flow;    }    return max_flow;}int main() {    int n = 6;  // 节点数量    // 初始化容量矩阵（示例图）    capacity[0][1] = 16; capacity[0][2] = 13;    capacity[1][2] = 10; capacity[1][3] = 12;    capacity[2][1] = 4;  capacity[2][4] = 14;    capacity[3][2] = 9;  capacity[3][5] = 20;    capacity[4][3] = 7;  capacity[4][5] = 4;    cout << "最大流为: " << edmondsKarp(0, 5, n) << endl;    return 0;}

算法二：Dinic 算法（更高效！）

Dinic算法是一种更高效的网络流算法，尤其适用于稠密图。它通过构建分层图（Level Graph）并进行多次 DFS 阻塞流（Blocking Flow）计算，时间复杂度为 O(V²·E)。

Dinic 的优势在于：一次 BFS 构建层次后，可以进行多次 DFS 增广，避免了 Edmonds-Karp 中频繁 BFS 的开销。

C++ 实现代码（简化版）

#include <iostream>#include <vector>#include <queue>#include <climits>using namespace std;struct Edge {    int to, rev, cap;    Edge(int t, int r, int c) : to(t), rev(r), cap(c) {}};vector<vector<Edge>> graph;vector<int> level;void add_edge(int u, int v, int cap) {    graph[u].emplace_back(v, graph[v].size(), cap);    graph[v].emplace_back(u, graph[u].size() - 1, 0);}bool bfs(int s, int t) {    fill(level.begin(), level.end(), -1);    queue<int> q;    q.push(s);    level[s] = 0;    while (!q.empty()) {        int u = q.front(); q.pop();        for (auto& e : graph[u]) {            if (e.cap > 0 && level[e.to] == -1) {                level[e.to] = level[u] + 1;                q.push(e.to);            }        }    }    return level[t] != -1;}int dfs(int u, int t, int flow) {    if (u == t) return flow;    for (auto& e : graph[u]) {        if (e.cap > 0 && level[e.to] == level[u] + 1) {            int f = dfs(e.to, t, min(flow, e.cap));            if (f > 0) {                e.cap -= f;                graph[e.to][e.rev].cap += f;                return f;            }        }    }    return 0;}int dinic(int s, int t) {    int max_flow = 0;    while (bfs(s, t)) {        int f;        while ((f = dfs(s, t, INT_MAX)) > 0) {            max_flow += f;        }    }    return max_flow;}int main() {    int n = 6;    graph.resize(n);    level.resize(n);    add_edge(0, 1, 16); add_edge(0, 2, 13);    add_edge(1, 2, 10); add_edge(1, 3, 12);    add_edge(2, 1, 4);  add_edge(2, 4, 14);    add_edge(3, 2, 9);  add_edge(3, 5, 20);    add_edge(4, 3, 7);  add_edge(4, 5, 4);    cout << "Dinic算法求得的最大流: " << dinic(0, 5) << endl;    return 0;}

如何选择算法？

• 对于小规模或稀疏图，Edmonds-Karp算法实现简单，易于调试。
• 对于大规模或竞赛场景，推荐使用Dinic算法实现，效率更高。
• 还有更高级的 Push-Relabel 等算法，但 Dinic 已能满足大多数需求。

总结

通过本文，你已经掌握了C++最大流算法的基本原理与两种主流实现方式。无论是学习网络流算法理论，还是准备算法竞赛，这些知识都至关重要。建议你动手敲一遍代码，修改测试用例，加深理解。

记住：算法不是死记硬背，而是理解+实践。祝你在算法之路上越走越远！