← all categories

Dinic d5c183c9

Dinic's max flow with capacity scaling: process augmenting paths in decreasing order of a capacity threshold (31 phases, thresholds 2^30 down to 2^0) so large-capacity paths get pushed first. The last phase (threshold 2^0) is always an unrestricted normal Dinic's pass, so correctness holds regardless of how large capacities are — scaling only affects how fast you get there. Prefer this over edmonds-karp.h. Source: kactl (CC0), see NOTICE.md.

Time: O(VE \log U), U = \max cap; O(E \sqrt V) for unit-capacity/bipartite-matching graphs. kactl-derived, tested

content/flows/dinic.h

template <typename T>
struct Dinic {
    struct Edge { int to, rev; T cap, cap0; T flow() { return max(cap0 - cap, T(0)); } };
    vector<vector<Edge>> adj;
    vector<int> lvl, ptr;
    int n;

    Dinic(int n) : adj(n), lvl(n), ptr(n), n(n) {}

    void addEdge(int a, int b, T cap, T rcap = 0) {
        adj[a].push_back({b, (int)adj[b].size(), cap, cap});
        adj[b].push_back({a, (int)adj[a].size() - 1, rcap, rcap});
    }

    T dfs(int v, int t, T f) {
        if (v == t || f == 0) return f;
        for (int &i = ptr[v]; i < (int)adj[v].size(); i++) {
            Edge &e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1) {
                if (T p = dfs(e.to, t, min(f, e.cap))) {
                    e.cap -= p;
                    adj[e.to][e.rev].cap += p;
                    return p;
                }
            }
        }
        return 0;
    }

    T maxflow(int s, int t) {
        T flow = 0;
        vector<int> q(n);
        q[0] = s;
        for (int shift = 30; shift >= 0; shift--) {
            do {
                fill(lvl.begin(), lvl.end(), 0);
                fill(ptr.begin(), ptr.end(), 0);
                int qi = 0, qe = 0;
                lvl[s] = 1;
                q[qe++] = s;
                while (qi < qe && !lvl[t]) {
                    int v = q[qi++];
                    for (auto &e : adj[v])
                        if (!lvl[e.to] && (e.cap >> shift)) { lvl[e.to] = lvl[v] + 1; q[qe++] = e.to; }
                }
                while (T p = dfs(s, t, numeric_limits<T>::max())) flow += p;
            } while (lvl[t]);
        }
        return flow;
    }
};