Build Lab: Dinic's Maximum Flow, Min-Cut Partitioning & Bipartite Matching Engine

Architecture of the Unified Dinic Flow & Matching Engine

Our production engine combines four essential engineering techniques:

1. Paired Arc Storage (arcs[2k], arcs[2k+1]): Every addEdge(u, v, cap) returns the forward arc index 2k, allowing callers to inspect the exact final flow on any edge via getEdgeFlow(edgeId) in $O(1)$ time.
2. Multi-Branch Blocking Flow DFS: Pushes multiple bottleneck branches from a single DFS invocation using the current-arc reference int& cid = ptr[u].
3. Zero-Cost Min-Cut Extraction from Final level[]: Because maxFlow(s, t) terminates precisely when bfs(s, t) fails to reach $t$, the level[u] array at termination already marks the exact residual reachability set $S = \{u : \text{level}[u] \ne -1\}$!
4. Bipartite Matching Adapter: Wraps $L \cup R$ into a unit network on $n_L + n_R + 2$ vertices and reads matched pairs directly from saturated $(u, v)$ arcs.

Complete Production C++20 Implementation: Unified Dinic Flow, Min-Cut & Matching Engine

#include <vector>
#include <queue>
#include <algorithm>
#include <limits>

class DinicEngine {
public:
    struct Arc {
        int from, to;
        long long cap;
    };

    explicit DinicEngine(int n) : n(n), adj(n), level(n, -1), ptr(n, 0) {}

    // Returns the forward arc index (even integer 2k)
    int addEdge(int u, int v, long long cap) {
        int id = static_cast<int>(arcs.size());
        adj[u].push_back(id);
        arcs.push_back({u, v, cap});
        adj[v].push_back(id + 1);
        arcs.push_back({v, u, 0});
        return id;
    }

    long long maxFlow(int s, int t) {
        long long totalFlow = 0;
        while (bfs(s, t)) {
            std::fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, t, std::numeric_limits<long long>::max())) {
                totalFlow += pushed;
            }
        }
        return totalFlow;
    }

    // Exact flow pushed along the edge returned by addEdge()
    long long getEdgeFlow(int edgeId) const noexcept {
        return arcs[edgeId ^ 1].cap;
    }

    // True iff vertex u belongs to the source side S of the minimum s-t cut
    bool inSourceSide(int u) const noexcept {
        return level[u] != -1;
    }

    std::vector<std::pair<int, int>> extractMinCutEdges() const {
        std::vector<std::pair<int, int>> cut;
        for (size_t id = 0; id < arcs.size(); id += 2) {
            const auto& e = arcs[id];
            if (level[e.from] != -1 && level[e.to] == -1 && (e.cap + arcs[id ^ 1].cap) > 0) {
                cut.emplace_back(e.from, e.to);
            }
        }
        return cut;
    }

private:
    int n;
    std::vector<Arc> arcs;
    std::vector<std::vector<int>> adj;
    std::vector<int> level, ptr;

    bool bfs(int s, int t) {
        std::fill(level.begin(), level.end(), -1);
        level[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int id : adj[u]) {
                int v = arcs[id].to;
                if (arcs[id].cap > 0 && level[v] == -1) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] != -1;
    }

    long long dfs(int u, int t, long long available) {
        if (available == 0 || u == t) return available;
        long long totalPushed = 0;
        for (int& cid = ptr[u]; cid < static_cast<int>(adj[u].size()); ++cid) {
            int id = adj[u][cid];
            int v = arcs[id].to;
            if (level[v] != level[u] + 1 || arcs[id].cap == 0) continue;

            long long tr = dfs(v, t, std::min(available - totalPushed, arcs[id].cap));
            if (tr == 0) continue;

            arcs[id].cap -= tr;
            arcs[id ^ 1].cap += tr;
            totalPushed += tr;
            if (totalPushed == available) return totalPushed;
        }
        return totalPushed;
    }
};