Dinic's Algorithm

C++ — Dinic

struct Dinic {
    struct Edge { int v, rev; long long cap; };
    vector> adj;
    vector level, ptr;
    int n;

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

    void add_edge(int u, int v, long long cap) {
        adj[u].push_back({v, (int)adj[v].size(), cap});
        adj[v].push_back({u, (int)adj[u].size() - 1, 0});
    }

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

    long long dfs(int u, int t, long long f) {
        if (u == t) return f;
        for (int& i = ptr[u]; i < adj[u].size(); i++) {
            auto& e = adj[u][i];
            if (e.cap > 0 && level[e.v] == level[u] + 1) {
                long long pushed = dfs(e.v, t, min(f, e.cap));
                if (pushed > 0) {
                    e.cap -= pushed;
                    adj[e.v][e.rev].cap += pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, t, LLONG_MAX))
                flow += pushed;
        }
        return flow;
    }
};

// O(V²E) general, O(E√V) bipartite. Use for all max flow problems.