---
tags: Graph Theory
title: Maximum Flow
---

## Dinic's Algorithm

### Sample Code

struct Dinic {
    Dinic(size_t N, int s, int t)
        : N(N), s(s), t(t), adj(N) {}

    struct Edge {
        int to;
        int cap;
        int rev;
        Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    size_t N;
    int s, t;

    vector<vector<Edge>> adj;
    vector<int> level;
    vector<size_t> index;

    void add_edge(int from, int to, int capacity) {
        adj[from].emplace_back(to, capacity, adj[to].size());
        adj[to].emplace_back(from, 0, adj[from].size() - 1);
    }

    bool bfs() {
        level.assign(N, -1);
        deque<int> q(1, s);
        level[s] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop_front();

            for (auto& e : adj[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push_back(e.to);
                }
            }
        }

        return level[t] >= 0;
    }

    int dfs(int u, int flow) {
        if (u == t) return flow;
        for (auto& i = index[u]; i < adj[u].size(); ++i) {
            auto& e = adj[u][i];
            if (e.cap > 0 && level[e.to] > level[u]) {
                int ret = dfs(e.to, min(flow, e.cap));
                if (ret > 0) {
                    e.cap -= ret;
                    adj[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }

    int max_flow() {
        int flow = 0;
        while (true) {
            if (!bfs()) return flow;
            index.assign(N, 0);
            int f;
            while ((f = dfs(0, 0x3fffffff)) > 0) {
                flow += f;
            }
        }
    }
};