C++实现最小割算法详解（从零开始掌握图论中的最大流最小割定理）

算法思路概述

我们将采用以下步骤实现最小割：

1. 构建图的邻接表表示，并记录每条边的容量。
2. 使用 Edmonds-Karp 算法（BFS 找增广路径）计算从 s 到 t 的最大流。
3. 在残量网络中，从 s 出发进行 DFS/BFS，所有能到达的节点构成集合 S，其余为 T。
4. 遍历原图中所有边，若起点在 S、终点在 T，则该边属于最小割。

C++ 代码实现

下面是一个完整的 C++ 实现，包含最大流计算和最小割提取：

#include <iostream>#include <vector>#include <queue>#include <climits>#include <algorithm>using namespace std;// 图的邻接表表示：每个节点存储 (邻居, 容量, 反向边索引)struct Edge {    int to, capacity, rev_index;    Edge(int t, int cap, int rev) : to(t), capacity(cap), rev_index(rev) {}};class MaxFlowMinCut {private:    vector<vector<Edge>> graph;    int n;public:    MaxFlowMinCut(int nodes) : n(nodes) {        graph.resize(n);    }    // 添加有向边 u->v，容量为cap    void addEdge(int u, int v, int cap) {        graph[u].push_back(Edge(v, cap, graph[v].size()));        graph[v].push_back(Edge(u, 0, graph[u].size() - 1)); // 反向边初始容量为0    }    // 使用BFS寻找增广路径（Edmonds-Karp）    int bfs(int s, int t, vector<int>& parent) {        fill(parent.begin(), parent.end(), -1);        queue<int> q;        q.push(s);        parent[s] = -2;        vector<int> min_capacity(n, 0);        min_capacity[s] = INT_MAX;        while (!q.empty()) {            int u = q.front(); q.pop();            for (int i = 0; i < graph[u].size(); ++i) {                Edge& e = graph[u][i];                if (parent[e.to] == -1 && e.capacity > 0) {                    parent[e.to] = u;                    min_capacity[e.to] = min(min_capacity[u], e.capacity);                    if (e.to == t) {                        return min_capacity[t];                    }                    q.push(e.to);                }            }        }        return 0; // 无法增广    }    // 计算最大流    int maxFlow(int s, int t) {        int total_flow = 0;        vector<int> parent(n);        while (int flow = bfs(s, t, parent)) {            total_flow += flow;            // 更新残量网络            int cur = t;            while (cur != s) {                int prev = parent[cur];                // 找到正向边并减少容量                for (auto& e : graph[prev]) {                    if (e.to == cur) {                        e.capacity -= flow;                        // 更新反向边                        graph[cur][e.rev_index].capacity += flow;                        break;                    }                }                cur = prev;            }        }        return total_flow;    }    // 获取最小割的边集    vector<pair<int, int>> getMinCut(int s) {        vector<bool> visited(n, false);        queue<int> q;        q.push(s);        visited[s] = true;        // 在残量网络中从s出发BFS，能到达的点属于S集合        while (!q.empty()) {            int u = q.front(); q.pop();            for (auto& e : graph[u]) {                if (e.capacity > 0 && !visited[e.to]) {                    visited[e.to] = true;                    q.push(e.to);                }            }        }        // 遍历所有原始边，找出从S到T的边        vector<pair<int, int>> cut_edges;        for (int u = 0; u < n; ++u) {            if (visited[u]) { // u in S                for (auto& e : graph[u]) {                    // 注意：只考虑原始图中的正向边（反向边容量初始为0）                    // 这里我们通过检查反向边是否来自非S集合来判断                    if (!visited[e.to] && e.capacity == 0) {                        // 说明这条边在原始图中存在且被完全饱和                        cut_edges.push_back({u, e.to});                    }                }            }        }        return cut_edges;    }};// 示例主函数int main() {    // 创建一个包含6个节点的图（0~5），设0为源点，5为汇点    MaxFlowMinCut mfmc(6);    // 添加边（u, v, 容量）    mfmc.addEdge(0, 1, 16);    mfmc.addEdge(0, 2, 13);    mfmc.addEdge(1, 2, 10);    mfmc.addEdge(1, 3, 12);    mfmc.addEdge(2, 1, 4);    mfmc.addEdge(2, 4, 14);    mfmc.addEdge(3, 2, 9);    mfmc.addEdge(3, 5, 20);    mfmc.addEdge(4, 3, 7);    mfmc.addEdge(4, 5, 4);    int max_flow = mfmc.maxFlow(0, 5);    cout << "最大流 = " << max_flow << endl;    auto min_cut = mfmc.getMinCut(0);    cout << "最小割包含的边（起点 -> 终点）:" << endl;    for (auto& edge : min_cut) {        cout << edge.first << " -> " << edge.second << endl;    }    return 0;}

代码说明

• addEdge 同时添加正向边和反向边，这是网络流算法的关键技巧。
• bfs 用于寻找一条从 s 到 t 的增广路径，并返回该路径上的最小剩余容量。
• maxFlow 不断调用 BFS 直到无法再增广，累计得到最大流。
• getMinCut 在最大流计算完成后，在残量网络中从 s 出发 BFS，标记可达节点（集合 S），然后找出所有从 S 到非 S 的原始边，即为最小割。

总结

通过本文，你已经掌握了如何用 C++ 实现 C++最小割算法。核心在于理解 最大流最小割定理，并利用 Edmonds-Karp 算法 求最大流。这种方法不仅高效（时间复杂度 O(VE²)），而且易于实现。

无论你是学习 图论最小割 的学生，还是需要解决实际问题的工程师，这套代码都能为你提供坚实基础。记住，最小割问题本质上是最大流问题的“另一面”，掌握其内在联系是关键！

希望这篇教程对你有帮助！如果你有任何疑问，欢迎在评论区留言交流。