compete::mcgill

Dinic (Max Flow)

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

Maximum flow with level-graph BFS plus blocking-flow DFS. 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.

// 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) {
        if (u == t) return f;
        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) {
                long long d = dfs(v, t, min(f, edges[id].cap));
                if (d > 0) {
                    edges[id].cap -= d;
                    edges[id ^ 1].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (long long d = dfs(s, t, LLONG_MAX)) flow += d;
        }
        return flow;
    }
};

// more matchings & flows

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