#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;
}