uniolympiads Ελληνικά

Maximum flow (Dinic)

The maximum flow from ss to tt and, from the last BFS, a minimum cut. Bipartite matching and disjoint paths build on it.

When

The signal is usually indirect: "the maximum number of pairs", "the minimum number of roads to close so that you cannot get from 11 to nn", "how many routes with no common edge". With nn up to a few hundred or thousand, flow is often the answer.

The idea

Every edge has a capacity and a reverse edge with capacity 0. When you push flow ff along an edge, its capacity drops by ff and the reverse edge's grows by ff. A later path can thus "take back" flow that was sent the wrong way.

Dinic works in phases:

  1. BFS from ss in the residual graph: every vertex gets a level.
  2. DFS that uses only edges from level ℓ\ell to ℓ+1\ell + 1, until no more flow fits (blocking flow). The pointer it[u] remembers which edge to continue from, so an edge that has "died" is not looked at again in the same phase.

The distance of tt grows strictly in every phase, so there are at most nn phases. Overall O(V2E)O(V^2 E) in the worst case, O(EV)O(E\sqrt{V}) for bipartite matching. In practice it is much faster.

Minimum cut. When it finishes, the vertices reached by the last BFS (level != -1) form the side of ss. The edges from them to the rest are a minimum cut, and its capacity equals the flow (max-flow min-cut theorem). The test verifies both, comparing against an enumeration of all cuts.

Three problems, one construction

  • Download Speed: the flow itself.
  • Police Chase: the minimum cut, with capacity 1 per road in both directions.
  • School Dance: source → boys (1), boy → girl (1), girls → sink (1). The flow is the maximum matching; the pairs are the boy → girl edges with saturated capacity.

Pitfalls

  • Undirected edge: two addEdge calls, one per direction.
  • The DFS is recursive, but its depth is at most the distance of tt, i.e. <n< n. For the sizes where flow is the right choice, that is safe.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/dinic.cpp
// Maximum flow, Dinic's algorithm. O(V^2 E) in general, O(E sqrt V) for bipartite matching.
// BFS builds the level graph; DFS sends blocking flow along edges with level[v] = level[u] + 1.
// it[u] remembers the next edge to try, so dead edges are not scanned twice in one phase.
// After maxFlow, the vertices with level != -1 form the source side of a minimum cut.

struct Dinic {
    struct Edge {
        int to;
        ll cap;
    };
    int n;
    vector<Edge> edges;
    vector<vector<int>> g;
    vector<int> level;
    vector<int> it;

    Dinic(int vertices) : n(vertices), g(vertices), level(vertices), it(vertices) {}

    // Edge i and its reverse i ^ 1 are stored next to each other.
    void addEdge(int u, int v, ll 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;
        level[s] = 0;
        q.push(s);
        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;
    }

    ll dfs(int u, int t, ll pushed) {
        if (u == t) {
            return pushed;
        }
        for (; it[u] < (int)g[u].size(); it[u]++) {
            int id = g[u][it[u]];
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == level[u] + 1) {
                ll got = dfs(v, t, min(pushed, edges[id].cap));
                if (got > 0) {
                    edges[id].cap -= got;
                    edges[id ^ 1].cap += got;
                    return got;
                }
            }
        }
        return 0;
    }

    ll maxFlow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (true) {
                ll f = dfs(s, t, LLONG_MAX);
                if (f == 0) {
                    break;
                }
                flow += f;
            }
        }
        return flow;
    }
};

Tested on 1,500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.