Ford-Fulkerson Max Flow

C++ — Ford-Fulkerson

struct Edge { int v, rev; long long cap; };
vector> adj;
vector vis;

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});  // reverse edge
}

long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    vis[u] = true;
    for (auto& e : adj[u]) {
        if (!vis[e.v] && e.cap > 0) {
            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 (true) {
        vis.assign(adj.size(), false);
        long long pushed = dfs(s, t, LLONG_MAX);
        if (pushed == 0) break;
        flow += pushed;
    }
    return flow;
}

// O(F × E) where F is max flow — bad for large flows.
// Use Edmonds-Karp (BFS) or Dinic instead.