最大流最小割问题中，最大流值等于最小割容量。Edmonds-Karp算法通过BFS寻找最短增广路径，确保O(V·E²)时间复杂度，C++实现基于残差图更新与反向边机制，支持重边处理并可提取最小割集合。
最大流最小割问题是网络流中的经典问题，目标是在一个有向图中从源点到汇点传输尽可能多的流量。Edmonds-Karp算法是Ford-Fulkerson方法的一种实现，使用BFS寻找增广路径，确保在多项式时间内求解。
基本概念
最大流：给定带权有向图，每条边有容量限制，求从源点 s 到汇点 t 的最大可能流量。
最小割：将图划分为两个部分，s 在其中一个部分，t 在另一个部分，割的容量是所有从前一部分指向后一部分的边容量之和，最小割即为其中最小的容量值。
根据最大流最小割定理，最大流的值等于最小割的容量。
Edmonds-Karp 算法原理
该算法基于以下思想：
- 不断使用 BFS 找从源点到汇点的一条增广路径（路径上每条边都有剩余容量）
- 沿该路径增加流量，更新残差图中正向边和反向边的容量
- 直到无法找到新的增广路径为止
BFS 的使用保证了每次选择最短路径，使时间复杂度稳定在 O(V·E²)，适合大多数实际应用。
C++ 实现代码
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
class MaxFlow {
private:
int n;
vector<vector<int>> capacity; // 容量矩阵
vector<vector<int>> adj; // 邻接表
public:
MaxFlow(int nodes) : n(nodes) {
capacity.resize(n, vector<int>(n, 0));
adj.resize(n);
}
// 添加边（包括反向边占位）
void addEdge(int u, int v, int cap) {
capacity[u][v] += cap; // 支持重边
adj[u].push_back(v);
adj[v].push_back(u); // 反向边用于残差图
}
// BFS 寻找增广路径并记录前驱
bool bfs(int s, int t, vector<int>& parent) {
fill(parent.begin(), parent.end(), -1);
parent[s] = -2;
queue<pair<int, int>> q; // (节点, 当前路径最小剩余容量)
q.push({s, INT_MAX});
while (!q.empty()) {
int u = q.front().first;
int flow = q.front().second;
q.pop();
for (int v : adj[u]) {
if (parent[v] == -1 && capacity[u][v] > 0) {
parent[v] = u;
int new_flow = min(flow, capacity[u][v]);
if (v == t) return true; // 找到汇点
q.push({v, new_flow});
}
}
}
return false;
}
// 计算从 s 到 t 的最大流
int maxFlow(int s, int t) {
int total_flow = 0;
vector<int> parent(n);
while (bfs(s, t, parent)) {
// 沿路径回溯计算可增广的流量
int path_flow = INT_MAX;
int cur = t;
while (cur != s) {
int prev = parent[cur];
path_flow = min(path_flow, capacity[prev][cur]);
cur = prev;
}
// 更新残差图
cur = t;
while (cur != s) {
int prev = parent[cur];
capacity[prev][cur] -= path_flow;
capacity[cur][prev] += path_flow;
cur = prev;
}
total_flow += path_flow;
}
return total_flow;
}
// 获取最小割：BFS 后仍能访问的节点属于 S 集
vector<bool> getMinCut(int s) {
vector<bool> visited(n, false);
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!visited[v] && capacity[u][v] > 0) {
visited[v] = true;
q.push(v);
}
}
}
return visited;
}
};
// 示例用法
int main() {
MaxFlow mf(6); // 节点数：0~5，设 0 为源点，5 为汇点
mf.addEdge(0, 1, 16);
mf.addEdge(0, 2, 13);
mf.addEdge(1, 2, 10);
mf.addEdge(1, 3, 12);
mf.addEdge(2, 1, 4);
mf.addEdge(2, 4, 14);
mf.addEdge(3, 2, 9);
mf.addEdge(3, 5, 20);
mf.addEdge(4, 3, 7);
mf.addEdge(4, 5, 4);
int max_flow = mf.maxFlow(0, 5);
cout << "最大流: " << max_flow << endl;
// 输出最小割
vector<bool> in_S = mf.getMinCut(0);
cout << "最小割中的边:" << endl;
for (int u = 0; u < 6; u++) {
for (int v = 0; v < 6; v++) {
// 原始输入中存在且跨越割的边
if (in_S[u] && !in_S[v]) {
// 这里仅示意，实际应结合初始图判断是否为原始边
cout << "边 " << u << " -> " << v << endl;
}
}
}
return 0;
}
关键细节说明
• 残差图维护：通过正向边减去流量、反向边加上流量来支持“撤销”操作
• 邻接表设计：即使没有直接连接也要加入反向边，确保 BFS 能遍历残差图
• 重边处理：使用 += 方式添加边容量，兼容多重边情况
• 最小割提取：最大流完成后，从源点出发在残差图中可达的所有节点构成集合 S，其余为 T，所有从 S 指向 T 的原始边构成最小割
基本上就这些。这个实现清晰、高效，适用于大多数网络流场景。注意节点编号从 0 开始，可根据需要调整。不复杂但容易忽略反向边和残差更新逻辑。调试时建议打印每轮增广后的残差状态。
立即学习“C++免费学习笔记（深入）”；
