i. Maximum Flow

Push as much flow as possible from $s$ to $t$ through capacitated directed edges. Every algorithm works on the residual graph (remaining capacity forward, already-sent flow backward) and stops when $t$ is unreachable; then the reachable set is a minimum cut, and max flow = min cut. Write Dinic: $O(V^{2}E)$ in general, $O(E\sqrt{V})$ for unit-capacity bipartite matching, $O(E\min (V^{2/3},E^{1/2}))$ for unit capacities, and much faster in practice. Modelling is in Flow Modeling.

Dinic

struct Dinic {
    struct E { int to; ll cap; };
    vector<E> e; vector<ll> orig; vector<vector<int>> g; vector<int> lvl, it;
    Dinic(int n) : g(n), lvl(n), it(n) {}
    int addEdge(int u, int v, ll c, ll rc = 0) {           // returns the id of the forward edge
        g[u].push_back(sz(e)); e.push_back({v, c}); orig.push_back(c);
        g[v].push_back(sz(e)); e.push_back({u, rc}); orig.push_back(rc);
        return sz(e) - 2;
    }
    bool bfs(int s, int t) {
        fill(all(lvl), -1); lvl[s] = 0; queue<int> q; q.push(s);
        while (sz(q)) { int u = q.front(); q.pop(); for (int id : g[u]) if (e[id].cap > 0 && lvl[e[id].to] < 0) lvl[e[id].to] = lvl[u] + 1, q.push(e[id].to); }
        return lvl[t] >= 0;
    }
    ll dfs(int u, int t, ll f) {
        if (u == t) return f;
        ll pushed = 0;
        for (int& i = it[u]; i < sz(g[u]); i++) {
            int id = g[u][i], v = e[id].to;
            if (e[id].cap <= 0 || lvl[v] != lvl[u] + 1) continue;
            ll d = dfs(v, t, min(f - pushed, e[id].cap));
            if (d) { e[id].cap -= d; e[id ^ 1].cap += d; pushed += d; if (pushed == f) return f; }
        }
        return pushed;
    }
    ll maxflow(int s, int t) {
        ll flow = 0;
        while (bfs(s, t)) { fill(all(it), 0); flow += dfs(s, t, LLONG_MAX); }
        return flow;
    }
    ll flowOn(int id) const { return orig[id] - e[id].cap; }  // flow on a forward edge
    bool sourceSide(int v) const { return lvl[v] >= 0; }     // after maxflow: S side of a minimum cut
};

• Undirected edge of capacity $c$: addEdge(u, v, c, c).
• Recursion depth is the level count, at most $V$.
• Capacity scaling (run phases only on edges with residual $\ge \Delta$, halving $\Delta$) gives $O(VE\log U)$ and helps on adversarial inputs with huge capacities.
• Push–relabel (highest label + gap heuristic) is the alternative for dense or hard graphs (Push-Relabel).
• Two implementation details do all the work above the naive DFS: storing each edge with its reverse at index id ^ 1 (so pushing flow back needs no lookup), and the current-arc pointer it[u] (so a phase never re-scans an edge it already gave up on). Drop either and Dinic degrades toward plain Ford–Fulkerson.
• ISAP (Improved Shortest Augmenting Path) is a related variant that maintains the level graph incrementally instead of rebuilding it every phase (via a gap heuristic on vertex levels), saving a constant factor in practice. Link-cut trees can push the blocking-flow step itself to $O(VE\log V)$ by representing the level graph as a dynamic forest, but this is essentially never worth the implementation cost in a contest.

Proof: max-flow min-cut and termination

Weak duality: for any flow $f$ and cut $(S,T)$ with $s\in S$, $t\in T$, the flow value equals (flow out of $S$) − (flow into $S$) $\le c(S,T)$. Strong duality: when no augmenting path exists, let $S$ be the vertices reachable from $s$ in the residual graph. Every edge from $S$ to $T$ is saturated and every edge from $T$ to $S$ carries zero flow (otherwise its reverse residual edge would extend $S$), so the flow value equals $c(S,T)$; by weak duality both are optimal. Integrality: with integer capacities every augmentation is integral, so an integral maximum flow exists. Dinic’s phases: let $d$ be the BFS distance from $s$ to $t$ in the residual graph. A blocking flow on the level graph saturates every shortest augmenting path; new residual edges point from level $i+1$ to level $i$, so any augmenting path afterwards uses a backward or skipping edge and has length $>d$. Hence at most $V-1$ phases. In one phase, the current-arc pointer means each edge is abandoned at most once, and each successful path has $\le V$ edges, giving $O(VE)$ per phase and $O(V^{2}E)$ total.

Proof sketch: $O(E\sqrt{V})$ on unit networks

In a unit network (unit capacities, every vertex other than $s,t$ has in-degree 1 or out-degree 1, e.g. bipartite matching), a phase costs $O(E)$. After $\sqrt{V}$ phases, the shortest augmenting path has length $\ge \sqrt{V}$; the remaining flow decomposes into vertex-disjoint augmenting paths in the residual graph, each of length $\ge \sqrt{V}$, so there are at most $\sqrt{V}$ of them and at most $\sqrt{V}$ more phases. Total $O(E\sqrt{V})$. For general unit-capacity graphs the same argument with edge-disjoint paths gives $O(E\sqrt{E})$, and with a level-cut counting argument $O(E{V}^{2/3})$.

Older algorithms (for understanding)

Algorithm	Augment along	Time
Ford–Fulkerson	any path	$O(E\cdot F)$, may not terminate with irrational capacities
Edmonds–Karp	shortest path (BFS)	$O(V{E}^2)$
capacity scaling	paths with residual $\ge \Delta$	$O(E^2\log U)$
Dinic	blocking flows on level graphs	$O(V^{2}E)$
MPM (Malhotra–Pramodh-Kumar–Maheshwari)	blocking flow by saturating the vertex of least throughput	$O(V^3)$
push–relabel (FIFO / highest label)	local pushes	$O(V^3)$ / $O(V^2\sqrt{E})$
Orlin / KRT	—	$O(VE)$, theoretical

Proof: Edmonds–Karp performs $O(VE)$ augmentations

BFS distances $d(v)$ from $s$ in the residual graph never decrease (the same argument as Dinic’s: augmenting along a shortest path only adds reverse edges going one level down). An edge $(u,v)$ is critical (saturated by an augmentation) only when $d(v)=d(u)+1$; before it can be critical again, flow must be sent back along $(v,u)$, which requires $d(u)=d(v)+1$ at that time, so $d(u)$ grew by at least 2. Distances are at most $V$, so each edge is critical $O(V)$ times, and each augmentation has a critical edge: $O(VE)$ augmentations of $O(E)$ each.

Reading the answer

• Flow on each edge: flowOn(id); decompose into at most $E$ paths and cycles by repeatedly walking positive-flow edges from $s$.
• Minimum cut: vertices with sourceSide(v) after the final BFS; cut edges are saturated edges from $S$ to $T$.
• Is edge $e$ in some / every min cut: Min Cut.
• Incremental flow: after adding an edge or raising a capacity, keep the residual graph and just run more phases; decreasing a capacity may require pushing flow back first.