compete::mcgill

Dinic (Max Flow)

O(V²E), O(E√V) bipartite

Maximum flow with level-graph BFS plus blocking-flow DFS. The DFS pushes every augmenting path in one pass and prunes dead vertices, which is the standard optimized version. Fast enough for essentially every contest flow problem, and on unit-capacity bipartite graphs it doubles as an O(E√V) matching algorithm. Edges are stored in pairs so edge id^1 is always the reverse edge, and after max_flow the vertices with level != -1 form the source side of a minimum cut.

// use it on

CSES: Download Speed ↗

Plain maximum flow from node 1 to node n. Build the graph with add_edge and call max_flow.

// the code

struct Dinic {
    struct Edge { int to; long long cap; };
    int n;
    vector<Edge> edges;
    vector<vector<int>> g;
    vector<int> level, it;
    Dinic(int n) : n(n), g(n), level(n), it(n) {}
    void add_edge(int u, int v, long long cap) {
        g[u].push_back(edges.size()); edges.push_back({v, cap});
        g[v].push_back(edges.size()); edges.push_back({u, 0});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int id : g[u])
                if (edges[id].cap > 0 && level[edges[id].to] == -1) {
                    level[edges[id].to] = level[u] + 1;
                    q.push(edges[id].to);
                }
        }
        return level[t] != -1;
    }
    long long dfs(int u, int t, long long f) {  // pushes a blocking flow
        if (u == t || f == 0) return f;
        long long pushed = 0;
        for (int& i = it[u]; i < (int)g[u].size(); i++) {
            int id = g[u][i], v = edges[id].to;
            if (edges[id].cap == 0 || level[v] != level[u] + 1) continue;
            long long d = dfs(v, t, min(f - pushed, edges[id].cap));
            edges[id].cap -= d;
            edges[id ^ 1].cap += d;
            pushed += d;
            if (pushed == f) return pushed;
        }
        if (pushed == 0) level[u] = -1;  // dead end, prune
        return pushed;
    }
    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
        // min cut: vertices with level != -1 are the source side
    }
};

// more matchings & flows

Bipartite Matching (Kuhn)Min-Cost Max-FlowHungarian Algorithm