Max Flow / Min Cut

Quick Revisit

• USE WHEN: Computing maximum flow from source to sink, or finding minimum cut separating two vertices
• INVARIANT: Max-flow = Min-cut; flow conservation at every non-source/sink vertex; residual graph has no s→t path when flow is maximum
• TIME: O(V²E) Dinic's general, O(E√V) unit-capacity | SPACE: O(V + E)
• CLASSIC BUG: Forgetting to add the reverse (backward) edge with capacity 0 — without it, flow can never be "undone" and the algorithm gets stuck at a suboptimal solution
• PRACTICE: 05-ladder-graphs

Given a directed graph with edge capacities, find the maximum flow from source $s$ to sink $t$ -- equivalently, the minimum cut separating them.

Difficulty: [Advanced]Prerequisites: BFS, Graph RepresentationCF Rating: 1900-2200+ ID: AL-24

Contest Frequency: * Specialized -- appears in modeling/reduction problems

---

Intuition

Consider this 5-node directed network with source $s$, sink $t$, and capacity 1 on every edge:

  s ---1---> A ---1---> C
  |          |          |
  |1         |1         |1
  |          v          v
  +---1----> B ---1---> t

Six edges: $s\to A$, $s\to B$, $A\to B$, $A\to C$, $B\to t$, $C\to t$. The maximum flow is 2 (route $s\to A\to C\to t$ and $s\to B\to t$, each carrying 1 unit).

Naive greedy: find any $s$-$t$ path, push as much flow as possible, repeat.

A DFS might discover $s\to A\to B\to t$ first:

  s -[1]-> A ---1---> C       Push 1 unit along s->A->B->t.
  |        |          |
  |1      [1]         |1      After: s->A saturated (0 left).
  |        v          v              B->t saturated (0 left).
  +---1--> B -[1]-> t
                               Next: s->B has capacity, but
  [1] = flow on this edge     B->t is full. Dead end.

                               Greedy halts at flow = 1.
                               Optimal = 2.

The greedy algorithm locked itself into a suboptimal routing. It sent flow through the "bridge" edge $A\to B$ that blocked both the $A\to C\to t$ and $s\to B\to t$ routes. Without a mechanism to undo this choice, the algorithm is stuck.

Residual edges let you "undo" bad decisions -- the max-flow min-cut theorem guarantees this always finds the optimal flow.

When you push $f$ units of flow along edge $(u,v)$ with capacity $c$:

• The forward residual capacity becomes $c-f$ (room to push more).
• A back edge $(v,u)$ with capacity $f$ appears (amount you can cancel).

The back edge is the key. It does not represent a real pipe -- it represents the option to reroute. If a later augmenting path traverses the back edge $(v,u)$, it effectively cancels $f$ units of flow on $(u,v)$ and redirects them elsewhere.

Analogy. Think of edges as water pipes with rated throughput. You start sending water along any route from source to sink. If you discover that one pipe is wasting capacity -- feeding a junction that is already bottlenecked downstream -- you can "pull back" water through a residual pipe (back edge) and redirect it along a less congested route. The max-flow min-cut theorem guarantees that this rerouting process always converges to the global optimum, no matter which paths you try first.

Visual Walkthrough -- Ford-Fulkerson on the small network

Same network as above. We run Ford-Fulkerson -- the idea of max flow, not the contest implementation. Repeatedly find any augmenting $s$-$t$ path in the residual graph, push the bottleneck flow, and update residual capacities. Ford-Fulkerson is the lens through which residual graphs make sense; Dinic's is the optimization that turns it into a contest-grade algorithm (we get to that below).

Step 1 -- Initial residual graph (= original network, flow = 0)

  s ---1---> A ---1---> C         Every forward edge has its
  |          |          |         full capacity available.
  |1         |1         |1        No back edges yet.
  |          v          v
  +---1----> B ---1---> t

Step 2 -- Augment along $s\to A\to B\to t$, push 1

  s ---0---> A ---1---> C         Forward residual capacities
  |          |          |         after pushing 1 unit.
  |1         |0         |1
  |          v          v         Back edges created:
  +---1----> B ---0---> t           A -> s  (cap 1)
                                    B -> A  (cap 1)
  Flow so far: 1                    t -> B  (cap 1)

Edges $s\to A$, $A\to B$, $B\to t$ are now saturated (residual 0). But the back edges open new paths in the residual graph.

Step 3 -- Augment along $s\to B\to A_{back}\to C\to t$, push 1

The back edge $B\to A$ (residual capacity 1) enables rerouting:

  Path in residual graph:

    s --1--> B --1--> A --1--> C --1--> t
              (back edge)

  Bottleneck = min(1, 1, 1, 1) = 1.  Push 1 unit.

Pushing flow through $B\to A$ cancels the earlier flow on $A\to B$. The net edge flows become:

  Edge    Flow          Edge    Flow
  -----   ----          -----   ----
  s -> A    1           A -> B    0  (cancelled!)
  s -> B    1           A -> C    1
  B -> t    1           C -> t    1

  Effective routing:  s -> A -> C -> t  (1 unit)
                      s -> B -> t       (1 unit)
  Total flow: 2

Step 4 -- No augmenting path: halt (max flow = min cut)

  Final forward residuals:

  s ---0---> A ---0---> C         From s in the residual graph:
  |          |          |         s -> A (0), s -> B (0).
  |0         |1         |0        s cannot reach any other node.
  |          v          v
  +---0----> B ---0---> t         No augmenting path exists.

  Min cut:
  +---------+   +-----------------+
  |  S-side |   |     T-side      |
  |         |   |                 |
  |    s    | / |  A   B   C   t  |
  |         |   |                 |
  +---------+   +-----------------+
  Cut edges: s->A (cap 1) + s->B (cap 1) = 2

  Max flow = min cut = 2.

The Invariant: Max-Flow Min-Cut Theorem

+-------------------------------------------------------------------+
|  INVARIANT                                                        |
|                                                                   |
|  At every step of the algorithm, the current flow is VALID:       |
|                                                                   |
|    Capacity:      0 <= f(u,v) <= c(u,v)   for every edge (u,v)   |
|    Conservation:  flow_in(v) = flow_out(v) for every v != s, t    |
|                                                                   |
|  TERMINATION CONDITION                                            |
|                                                                   |
|    No augmenting s-t path exists in the residual graph.           |
|    By the max-flow min-cut theorem, this implies:                 |
|                                                                   |
|      current flow = maximum flow = minimum cut capacity           |
|                                                                   |
|  The set of nodes reachable from s in the final residual graph    |
|  is the S-side of the minimum cut. Edges crossing from S-side     |
|  to T-side (with original capacity > 0) form the cut.             |
+-------------------------------------------------------------------+

Why this works: every augmentation increases total flow by at least 1 (for integer capacities), and flow is bounded by the minimum cut capacity. So the algorithm terminates in at most $O(|f^{\ast }|)$ iterations, where $f^{\ast }$ is the max flow value. Using BFS to find shortest augmenting paths (Edmonds-Karp) tightens this to $O(VE)$ iterations. Using level graphs and blocking flows (Dinic's) gives $O(V^{2}E)$ total.

From Ford-Fulkerson to Dinic

Ford-Fulkerson is the explanation; Dinic is the contest implementation. The hand-off has three steps:

1. BFS gives shortest augmenting paths. Picking any augmenting path can repeat work; BFS gives shortest paths in the residual graph and groups vertices into levels $\text{level}[v]$ = BFS distance from $s$.
2. Restrict augmentation to the "level graph." Only follow residual edges $u\to v$ with $\text{level}[v]=\text{level}[u]+1$. The level graph is acyclic and changes only $O(V)$ times.
3. Find a blocking flow per phase. A blocking flow saturates at least one edge on every $s$-$t$ path in the level graph. After each blocking flow you rebuild the level graph; the level of $t$ strictly increases, so $O(V)$ phases suffice.

Each phase costs $O(VE)$, so Dinic runs in $O(V^{2}E)$ in general and $O(E\sqrt{V})$ on unit-capacity graphs (e.g. bipartite matching). The implementation below uses the standard "current-arc" optimisation: an iterator $\text{iter}[v]$ remembers which neighbour we last tried, so we never re-scan dead-end edges within a phase.

When to Reach for This

Trigger phrases -- if you see any of these, think max flow:

Trigger	Reduction
"maximum flow" / "minimum cut"	Direct application
"bipartite matching"	Source -> left, right -> sink, all caps 1
"edge-disjoint paths"	All caps 1, answer = max flow (Menger's theorem)
"vertex-disjoint paths"	Split each vertex into in/out, cap 1 on internal edge
"minimum path cover" (DAG)	$n$ minus maximum bipartite matching
"partition into two groups with min cost"	Min cut separation
"project selection" / "closure"	Source/sink modeling with infinity edges

Counter-examples -- these look similar but are NOT flow problems:

• "Shortest path from $s$ to $t$" -- use Dijkstra or BFS, not flow.
• "Minimum spanning tree" -- use Kruskal or Prim, not flow.
• "Maximum independent set" -- NP-hard in general; flow does not help.
• "Maximum matching in a general (non-bipartite) graph" -- use the Blossom algorithm; flow-based approaches only handle bipartite graphs.
• "Minimum cost flow" -- related, but a harder generalization; requires SPFA-based augmentation or cost-scaling, not plain max flow.

  FLOW MODELING DECISION TREE:

  Problem mentions "maximum/minimum" + "partition/cut"?
    |
    YES --> Min cut (source=group A, sink=group B)
    |
    NO --> Problem mentions "matching" in bipartite graph?
            |
            YES --> Max flow with all caps = 1
            |
            NO --> Problem mentions "disjoint paths"?
                    |
                    YES --> Edge-disjoint: caps = 1
                    |       Vertex-disjoint: split nodes
                    |
                    NO --> Problem has costs per edge?
                            |
                            YES --> Min-cost flow (different topic)
                            |
                            NO --> Direct max flow

What the Code Won't Teach You

The algorithm is the easy part; the modeling is the hard part. Dinic's struct is ~40 lines you can memorize. But staring at a problem about assigning students to dorm rooms and realizing "this is min cut with source = dorm A preference, sink = dorm B preference, penalty edges for roommate conflicts" -- that is a completely separate skill. You build it by solving 20+ flow modeling problems, not by re-reading the algorithm.

Back edges are not a hack -- they are the algorithm's conscience. Every back edge says: "you can undo this decision." Without them, flow is a greedy that gets stuck. The moment you internalize back edges as "undo options, not real pipes," residual graphs stop being confusing and start being obvious.

  WHY BACK EDGES MATTER -- the undo mechanism:

  Forward edge (u->v, cap 5):     Back edge (v->u, cap 0):
  "You may send up to 5 units"   "You may undo 0 units"
          |                               |
  After pushing 3 units:         After pushing 3 units:
          |                               |
  Forward (u->v, cap 2):          Back (v->u, cap 3):
  "2 more units allowed"         "You can undo up to 3"
          |                               |
          +---------- KEY POINT ----------+
          |                               |
  The back edge doesn't represent   It represents the OPTION
  a real pipe in the network.       to reroute flow elsewhere.

The min-cut is often the real answer, not the flow value. Many problems disguised as "partition into two groups" or "minimum edges to disconnect" are really asking for the min cut. After max_flow(), recovering which edges form the cut (BFS reachability on the residual) is the step that actually answers the problem.

---

C++ STL Reference

Function / Class	Header	What it does	Relevance
vector<T>	<vector>	Edge list storage, adjacency list via vector<vector<int>>	Core graph structure
queue<T>	<queue>	BFS for building level graph	Dinic's BFS phase
fill(begin, end, val)	<algorithm>	Reset level/iterator arrays	Per-phase reset
min(a, b)	<algorithm>	Bottleneck computation on augmenting path	DFS phase
numeric_limits<T>::max()	<limits>	Represent infinity for initial flow bound	DFS call
memset(arr, val, size)	<cstring>	Fast array zeroing (level array reset)	Optional optimization

---

Implementation

Three Critical Implementation Details

1. Reverse edges are mandatory. For every edge u->v with capacity c, add a reverse edge v->u with capacity 0. The reverse edge allows the algorithm to "undo" flow. Store edges in pairs: edge at index i has its reverse at index i^1 (use XOR trick by always adding edges in pairs starting from an even index).

2. Reset iter[] each phase (Dinic's). The iter[] array (current-arc optimization) must be reset to the start of each adjacency list at the beginning of every blocking-flow phase. Forgetting this makes the algorithm incorrect (not just slow).

3. Undirected edges = two directed edges. For an undirected edge (u,v) with capacity c, add u->v with cap c AND v->u with cap c (each with its own reverse edge of cap 0). Total: 4 edge entries per undirected edge.

Version 1: Minimal Contest Template (Dinic's Algorithm)

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, rev; long long cap; };

struct Dinic {
    int n;
    vector<vector<Edge>> g;
    vector<int> level, iter;

    Dinic(int n) : n(n), g(n), level(n), iter(n) {}

    void add_edge(int from, int to, long long cap) {
        g[from].push_back({to, (int)g[to].size(), cap});
        g[to].push_back({from, (int)g[from].size() - 1, 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 v = q.front(); q.pop();
            for (auto& e : g[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int& i = iter[v]; i < (int)g[v].size(); i++) {
            Edge& e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            long long d;
            while ((d = dfs(s, t, numeric_limits<long long>::max())) > 0)
                flow += d;
        }
        return flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    Dinic din(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        u--; v--;
        din.add_edge(u, v, c);
    }
    cout << din.max_flow(0, n - 1) << "\n";
    return 0;
}

Version 2: Explained Version

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;     // destination vertex
    int rev;    // index of reverse edge in g[to]
    long long cap;  // residual capacity (not original capacity)
};

struct Dinic {
    int n;
    vector<vector<Edge>> g;  // adjacency list of edges (forward + backward)
    vector<int> level;        // BFS distance from source (-1 = unreachable)
    vector<int> iter;         // current edge index for DFS (avoids re-scanning dead ends)

    Dinic(int n) : n(n), g(n), level(n), iter(n) {}

    // Add directed edge from->to with given capacity.
    // Also adds reverse edge to->from with capacity 0.
    // The reverse edge is how we model "undoing" flow.
    void add_edge(int from, int to, long long cap) {
        g[from].push_back({to, (int)g[to].size(), cap});
        g[to].push_back({from, (int)g[from].size() - 1, 0});
        // For undirected edges: add cap to both directions, i.e.,
        // call add_edge(from, to, cap) and add_edge(to, from, cap).
        // Or set the reverse edge's cap to cap as well.
    }

    // BFS phase: compute shortest-path levels from s in the residual graph.
    // Returns true if t is reachable (so more flow can be pushed).
    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 v = q.front(); q.pop();
            for (auto& e : g[v]) {
                // Only traverse edges with remaining capacity
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    // DFS phase: find an augmenting path in the level graph.
    // f = flow we can still push from v towards t.
    // iter[v] tracks which edges we already tried -- this is the
    // "current arc" optimization that makes Dinic's fast.
    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        // Start from iter[v], not 0 -- skip edges already known to be dead ends.
        for (int& i = iter[v]; i < (int)g[v].size(); i++) {
            Edge& e = g[v][i];
            // Only go "downhill" in the level graph (level increases by 1)
            if (e.cap > 0 && level[v] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;              // reduce forward capacity
                    g[e.to][e.rev].cap += d; // increase reverse capacity
                    return d;
                }
            }
        }
        return 0;  // no augmenting path from v
    }

    // Main loop: BFS to build level graph, then DFS to find blocking flows.
    // Repeat until t is unreachable from s.
    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            // Reset current-arc pointers for new phase
            fill(iter.begin(), iter.end(), 0);
            long long d;
            // Push multiple augmenting paths in one phase
            while ((d = dfs(s, t, numeric_limits<long long>::max())) > 0)
                flow += d;
        }
        return flow;
    }

    // After max_flow(), find which nodes are on the S-side of the min cut.
    // An edge (u,v) is in the min cut iff level[u] >= 0 and level[v] < 0
    // and the original capacity was > 0.
    vector<bool> min_cut_side() {
        vector<bool> s_side(n);
        for (int i = 0; i < n; i++)
            s_side[i] = (level[i] >= 0);
        return s_side;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    Dinic din(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        u--; v--;
        din.add_edge(u, v, c);
    }

    long long ans = din.max_flow(0, n - 1);
    cout << ans << "\n";

    // Optional: recover the min cut
    // vector<bool> side = din.min_cut_side();
    // for (int u = 0; u < n; u++)
    //     for (auto& e : din.g[u])
    //         if (side[u] && !side[e.to] && /* original cap > 0 */)
    //             // edge (u, e.to) is in the min cut

    return 0;
}

---

Operations Reference

Operation	Time	Space
Build graph (add_edge $\times m$)	$O(m)$	$O(V+E)$ -- each edge stores forward + reverse
Single BFS phase	$O(V+E)$	$O(V)$ for level array + queue
Single blocking flow (DFS)	$O(VE)$	$O(V)$ recursion stack
Dinic's total	$O(V^{2}E)$	$O(V+E)$
Dinic's on unit-capacity graphs	$O(E\sqrt{V})$	$O(V+E)$
Dinic's on bipartite matching	$O(E\sqrt{V})$	$O(V+E)$
Recover min cut (BFS on residual)	$O(V+E)$	$O(V)$

Practical note: Dinic's with the current-arc optimization handles $V\le 5000$, $E\le 50000$ easily within 2-3 seconds on CF. For $V\le 500$, even ${10}^5$ edges are fine.

  DINIC'S PHASES -- what happens in each iteration:

  Phase 1: BFS builds level graph     Phase 2: DFS finds blocking flows
  +-----------------------------+     +-----------------------------+
  | s -(1)-> A -(2)-> B -(3)-> t|     | Walk level graph top-down   |
  |    level 0   1       2    3  |     | Push flow along s->...->t     |
  |                              |     | iter[] skips dead-end edges |
  | Only edges to next level     |     | Multiple paths per phase    |
  +-----------------------------+     +-----------------------------+
           |                                   |
           v                                   v
  Repeat until BFS can't reach t         Each phase: O(VE) blocking flow
  (= no augmenting path exists)          Total phases: O(V)
                                         Total: O(V²E)

---

Problem Patterns

Pattern 1: Direct Max Flow

The problem explicitly asks for maximum flow or minimum cut in a network.

Read the graph, build the network, run Dinic's. Check whether the problem uses 0-indexed or 1-indexed vertices.

CF examples: CF 1082G, CF 546E

Pattern 2: Min Cut as Separation

Partition objects into two groups with minimum cost. Each object has a cost for being in group A vs group B, plus penalty edges for adjacent objects in different groups.

Model: source = group A, sink = group B. Edge from $s$ to node $i$ with capacity = cost of putting $i$ in group B. Edge from $i$ to $t$ with capacity = cost of putting $i$ in group A. Penalty edges between adjacent nodes.

s --cost_B[i]--> i --cost_A[i]--> t
i --penalty[i][j]--> j  (and j --> i if undirected)

CF examples: CF 1082G, CF 1399F

Pattern 3: Project Selection / Closure Problem

Given projects with profits (positive or negative) and dependency constraints (must take project $A$ before $B$), maximize total profit.

Model: Add $s$ to each positive-profit project with capacity = profit. Add each negative-profit project to $t$ with capacity = $|$profit$|$. Add $\mathrm{\infty }$-capacity edges for dependencies. Answer = sum of positive profits $-$ max flow.

CF examples: CF 1082G, CF 311E

Pattern 4: Bipartite Matching via Flow

Maximum matching in a bipartite graph = max flow in a network with source connected to left side, right side connected to sink, all capacities 1.

Dinic's runs in $O(E\sqrt{V})$ on unit-capacity bipartite graphs -- same as Hopcroft-Karp.

s --1--> L_i --1--> R_j --1--> t

CF examples: CF 1139E, CF 1592F1

Pattern 5: Minimum Path Cover in DAG

Minimum number of vertex-disjoint paths to cover all vertices in a DAG = $n - $ maximum bipartite matching. Split each vertex into in-copy and out-copy, add edges matching the DAG structure.

CF examples: CF 590C

Pattern 6: Maximum Weight Closure

Select a subset of vertices in a directed graph such that if you select $v$, you must also select all vertices reachable from $v$. Maximize total weight.

Identical to project selection (Pattern 3). Very common disguise.

CF examples: CF 1082G

Pattern 7: Edge-Disjoint Paths

Maximum number of edge-disjoint $s$-$t$ paths = max flow with all capacities 1 (Menger's theorem). For vertex-disjoint paths, split each vertex into in/out with capacity 1.

CF examples: CF 653D

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                MAX FLOW / MIN CUT CHEAT SHEET                |
+--------------------------------------------------------------+
| WHEN TO USE:                                                 |
|   - "Minimum cut" / "maximum flow" in statement             |
|   - Partition into 2 groups with min cost                    |
|   - Project selection / closure with dependencies            |
|   - Bipartite matching (Dinic = Hopcroft-Karp speed)        |
|   - Edge/vertex-disjoint paths                               |
+--------------------------------------------------------------+
| TEMPLATE:                                                    |
|   Dinic din(n);                                              |
|   din.add_edge(u, v, cap);  // auto-adds reverse edge       |
|   long long ans = din.max_flow(s, t);                        |
+--------------------------------------------------------------+
| COMPLEXITY:                                                  |
|   Time:  O(V^2 * E) general, O(E * sqrt(V)) unit-cap       |
|   Space: O(V + E)                                            |
+--------------------------------------------------------------+
| MIN CUT RECOVERY:                                            |
|   After max_flow, BFS on residual from s.                    |
|   S-side = reachable. Cut edges: u reachable, v not.         |
+--------------------------------------------------------------+
| GOTCHAS:                                                     |
|   - Reverse edges are mandatory (cap 0 initially)            |
|   - Reset iter[] each BFS phase                              |
|   - Use long long if capacities > 2*10^9                     |
|   - Undirected edge = two directed edges (cap both ways)     |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Reverse edges. Every add_edge(u, v, cap) must also add a reverse edge (v, u, 0). Forgetting this is the #1 bug. The rev index links them.

Undirected edges. For undirected graphs, either call add_edge(u, v, cap) and add_edge(v, u, cap), or add one edge with both forward and backward capacity set to cap. Do not add a single directed edge -- the reverse with cap 0 is not the same as an undirected edge.

Integer overflow. If capacities are up to ${10}^9$ and you have $\sim {10}^5$ edges, total flow can exceed int. Use long long for capacity and flow. The initial DFS bound numeric_limits<long long>::max() is fine.

Multiple edges. Parallel edges between the same pair of vertices are allowed. The edge-list representation handles this naturally; adjacency matrix does not.

Resetting iter[]. The current-arc array must be reset to all zeros at the start of each BFS phase. Forgetting this makes the DFS skip valid edges and produces wrong answers.

0-index vs 1-index. Off-by-one on vertex numbering is common. If the problem uses 1-indexed vertices, either subtract 1 when reading or allocate n+1 vertices.

Debugging flow. To verify correctness, after max_flow(), check:

• Sum of flow out of $s$ = sum of flow into $t$ = returned value.
• For each edge, $0\le$ flow $\le$ capacity.
• Flow conservation at every non-source, non-sink vertex.

You can print flow on each edge as original_cap - residual_cap for forward edges.

TLE tips.

• Dinic's should be $<1$ second for $V\le 1000$, $E\le 10000$ on CF.
• If TLE, check you're not accidentally creating $O(V^2)$ edges.
• Scaling the capacity type from long long to int can help if caps fit in int.

Mental Traps

Trap 1: "I understand Dinic's, therefore I can solve flow problems."

Understanding the algorithm and modeling a problem as a flow network are orthogonal skills. You can implement Dinic's perfectly and still stare blankly at "partition students into groups minimizing conflict cost." The modeling muscle -- source/sink placement, capacity assignment, infinity edges for hard constraints -- requires solving dozens of flow reductions.

  THE FLOW PROBLEM PIPELINE:

  +------------------+     +------------------+     +-----------+
  | Read problem     | --> | Model as network | --> | Run Dinic |
  | (hard: 80% of   |     | (the REAL skill) |     | (easy:    |
  |  the work)       |     |   s, t, caps,    |     |  template |
  |                  |     |   node splitting |     |  code)    |
  +------------------+     +------------------+     +-----------+
        ^                         |
        |    Most people focus    |
        |    HERE (algorithm)     |
        |    but struggle HERE ---+
        |    (modeling)

Trap 2: "Min cut = the single bottleneck edge."

Min cut is a partition of all nodes into S-side and T-side, not a single edge. The cut capacity is the sum of capacities of all edges crossing from S to T. A graph can have a min cut with 50 edges, none of which is individually the bottleneck of any path.

  WRONG mental model:          RIGHT mental model:

  s --[3]--> A --[2]--> t     S-side    T-side
       bottleneck = 2?         +-----+  +-------+
                               | s A |  | B C t |
  ACTUALLY:                    +-----+  +-------+
  s --[3]--> A --[2]--> t        |  cut edges  |
  s --[3]--> B --[2]--> t        s->B (cap 3)   |
  A --[5]--> C --[2]--> t        A->C (cap 5)   |
                                  total cut = 8
  Min cut might be {s}|{rest}     (not any single edge)
  with total = 3+3 = 6

---

Common Mistakes

1. Missing reverse edges. Dinic's returns flow 0 on a graph with clearly positive flow when you add the forward edge $(u,v,c)$ but forget to add the reverse edge $(v,u,0)$. Without reverse edges, Dinic's BFS finds no augmenting paths because it can't "undo" flow -- the residual graph is the cornerstone of every augmenting-path algorithm. Always add edges in pairs: forward with capacity $c$, reverse with capacity $0$.

Debug Drills

Drill 1 -- Missing reverse edges

void add_edge(int from, int to, int cap) {
    graph[from].push_back({to, cap, 0});
    // Missing: graph[to].push_back({from, 0, 0});
}

What's wrong?

Every edge needs a reverse edge with capacity 0 in the residual graph. Without it, flow cannot be "pushed back" and the algorithm fails:

void add_edge(int from, int to, int cap) {
    graph[from].push_back({to, cap, 0, (int)graph[to].size()});
    graph[to].push_back({from, 0, 0, (int)graph[from].size() - 1});
}

Drill 2 -- BFS includes saturated edges

// Dinic's BFS to build level graph
void bfs(int s) {
    queue<int> q;
    q.push(s);
    level[s] = 0;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto& e : graph[v]) {
            if (level[e.to] == -1) {  // BUG: doesn't check residual capacity
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

What's wrong?

The BFS must only traverse edges with positive residual capacity (e.cap - e.flow > 0). Without this check, the level graph includes saturated edges that can't carry more flow:

if (level[e.to] == -1 && e.cap - e.flow > 0) {

Drill 3 -- DFS without current-arc optimization

int dfs(int v, int t, int pushed) {
    if (v == t) return pushed;
    for (int i = 0; i < graph[v].size(); i++) {  // restarts from 0 each time!
        // ...
    }
}

What's wrong?

Without the current-arc (iter[]) optimization, the DFS revisits edges that have already been fully explored, causing $O(V{E}^2)$ instead of $O(V^{2}E)$. Use an iter[v] pointer that remembers where to resume:

for (int& i = iter[v]; i < graph[v].size(); i++) {

Self-Test

Before moving on, verify you can answer these without looking at the notes:

• [ ] Write the Dinic's add_edge function from memory -- including the reverse edge with capacity 0 and the rev index linking forward and back edges.
• [ ] Explain with a 4-node example why greedy augmentation (no back edges) fails, and how back edges fix it.
• [ ] Model bipartite matching as max flow -- draw the network with source, left nodes, right nodes, sink, and all capacities set to 1.
• [ ] After running max_flow(), recover the min cut: which nodes are on the S-side (reachable from source in the residual), and which edges form the cut.
• [ ] Convert an undirected edge $(u,v,c)$ into the correct flow representation -- two directed edges, each with its own reverse edge (4 edge entries total).

---

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Understand the concept of flow and cuts in a network.
1500	Implement Dinic's algorithm; solve direct max-flow problems.
1800	Model problems as flow networks (project selection, bipartite matching via flow, closure problems).
2100	Min-cut recovery (find the actual cut edges); combine flow with DP or binary search; handle large networks with special structure.

#	Problem	Source	Difficulty	Key Idea
1	Maximum Flow	CSES	Easy	Direct max flow template check
2	Download Speed	CSES	Easy	Direct max flow on a network
3	Police Chase	CSES	Medium	Min cut -- find and output the cut edges
4	CF 546E	CF	Medium	Flow on bipartite-style graph
5	CF 1082G	CF	Medium	Project selection / max weight closure
6	CF 653D	CF	Medium	Delivery planning with flow
7	CF 311E	CF	Hard	Bipartite min cut with grid structure
8	CF 1592F1	CF	Hard	Matching + flow reduction
9	Minimum Path Cover	CSES	Medium	DAG path cover via bipartite matching
10	CF 1439C	CF	Hard	Flow with construction / greedy hybrid

---

Further Reading

• cp-algorithms: Maximum Flow -- Dinic's Algorithm -- detailed proof and implementation.
• cp-algorithms: Maximum Flow -- Ford-Fulkerson and Edmonds-Karp -- foundational methods, useful for understanding residual graphs.
• cp-algorithms: Minimum Cut -- min cut recovery and applications.
• CF Blog: Flow Problems Collection -- curated list of flow problems with editorial links.
• TopCoder: Max Flow Tutorial -- clear beginner-friendly explanation.
• See: BFS -- needed for Dinic's level graph construction.
• See: Graph Representation -- edge-list adjacency representation used here.
• See: Bipartite Matching -- specialized algorithms when full Dinic's is overkill.