• Overview and Terminology
• Ford–Fulkerson (augmenting paths)
• Edmonds–Karp (BFS shortest augmenting paths)
• Dinic (level graph + blocking flow)
• Min-Cut and Max-Flow Theorem
• Exercises

• Network: directed graph with capacities c(u,v) ≥ 0, source s, sink t.
• Flow: f(u,v) within capacity and obeying conservation (except at s,t).
• Residual graph: edges with residual capacity c(u,v) - f(u,v) and back-edges f(u,v).

// Dinic below includes a full residual graph structure. This is the FF idea:
// Repeatedly find any s->t path in residual graph and augment by its bottleneck.

• Note: with irrational capacities, FF may not terminate; with integers it terminates.

Uses BFS on the residual graph to get the shortest augmenting path in number of edges, guaranteeing O(n·m²) time.

// Dinic's algorithm implementation (adjacency list of edges with rev indices)
function Dinic(n) {
  const level = Array(n).fill(0);
  const it = Array(n).fill(0);
  const G = Array.from({length: n}, () => []);
  function addEdge(u, v, c) {
    const a = { to: v, cap: c, rev: null };
    const b = { to: u, cap: 0, rev: a };
    a.rev = b; G[u].push(a); G[v].push(b);
  }
  function bfs(s, t) {
    level.fill(-1); const q = []; level[s] = 0; q.push(s);
    for (let qi = 0; qi < q.length; qi++) {
      const u = q[qi];
      for (const e of G[u]) if (e.cap > 0 && level[e.to] < 0) {
        level[e.to] = level[u] + 1; q.push(e.to);
      }
    }
    return level[t] >= 0;
  }
  function dfs(u, t, f) {
    if (u === t) return f;
    for (let i = it[u]; i < G[u].length; i++, it[u] = i) {
      const e = G[u][i];
      if (e.cap > 0 && level[e.to] === level[u] + 1) {
        const ret = dfs(e.to, t, Math.min(f, e.cap));
        if (ret > 0) { e.cap -= ret; e.rev.cap += ret; return ret; }
      }
    }
    return 0;
  }
  function maxFlow(s, t) {
    let flow = 0;
    while (bfs(s, t)) {
      it.fill(0);
      for (;;) { const pushed = dfs(s, t, 1e18); if (!pushed) break; flow += pushed; }
    }
    return flow;
  }
  // Optional: retrieve min-cut after maxFlow by nodes with level >= 0 in last BFS from s
  function minCutSet(s) {
    // after running maxFlow, run bfs(s, t) without resetting residuals; nodes with level != -1 are on s-side
    return level.map((lv, i) => lv !== -1 ? i : -1).filter(i => i !== -1);
  }
  return { addEdge, maxFlow, minCutSet };
}

• Complexity: O(m·n^2) general; faster on unit networks and bipartite graphs.
• Trick: store reverse edges for constant-time residual updates.

• Max-flow min-cut theorem: value of max flow equals capacity of minimum s-t cut.
• Recovering a cut: nodes reachable from s in the final residual graph give the s-side of a min cut.
• Applications: bipartite matching, image segmentation, circulation with demands.

1. Implement Edmonds–Karp on top of the same residual graph structure and compare vs. Dinic.
2. Use Dinic to compute maximum bipartite matching by building a flow network.
3. After computing max flow, recover an explicit min cut (S, T) partition.