iii. Flow Modeling

Most flow problems are modelling problems. The code below reuses Dinic from Max Flow (addEdge returns the edge id, flowOn(id), sourceSide(v)).

Choosing an algorithm

Problem shape	Tool
maximum $s$–$t$ flow, or min cut by LP duality	Max Flow (Dinic)
dense graph, unit capacities, or flow is the bottleneck over max-flow’s bound	Push-Relabel
is edge $e$ in every / some minimum cut; min cut after a capacity change	Minimum Cut
cheapest cut over all vertex pairs, undirected graph	Global Minimum Cut (Stoer–Wagner)
many pairwise min-cut queries on the same undirected graph	Gomory–Hu Tree
flow with per-unit costs, or lower bounds / supplies-and-demands	Min-Cost Flow
assign $n$ agents to $n$ (or $m\ge n$) slots minimising total cost, dense bipartite	Assignment Problem (Hungarian, $O(n^3)$) — min-cost flow also works but is slower on dense inputs
maximum matching, bipartite, unweighted	Bipartite Matching (Kuhn’s / Hopcroft–Karp)
maximum matching, general graph, unweighted	General Matching (Blossom)
maximum-weight matching, general graph	Weighted General Matching
independent set largest in two matroids simultaneously	Matroid Intersection
two-sided preferences, no total cost to optimise, want stability not maximum weight	Stable Matching (Gale–Shapley) — this is not an optimization problem over a single objective, which is why it needs its own algorithm rather than falling out of weighted matching

Max-flow min-cut (proved there) is the reason the first several rows all reduce to the same machinery; stable matching is the odd one out precisely because “stable” isn’t a weight to maximize.

Construction patterns

Requirement	Construction
several sources / sinks	super-source / super-sink with capacity = supply / demand
vertex capacity $c_v$	split $v_{\text{in}}\to v_{\text{out}}$ with capacity $c_v$
$k$ edge-disjoint / vertex-disjoint paths	unit capacities (split vertices for vertex-disjoint); Menger
bipartite matching / $b$-matching	$s\to L$ (cap 1 or $b_u$), $L\to R$ (cap 1), $R\to t$ (cap 1 or $b_v$)
each item assigned to one of its allowed slots, slot capacities	the same, with slot capacities on $R\to t$
time-expanded problems (people moving over $T$ steps)	a copy of every vertex per time step, waiting edges $v_t\to v_{t+1}$
lower bounds $\ell \le f\le c$	demands transformation below
”choose $u$ ⟹ must choose $v$”, profits and costs	maximum weight closure (min cut)
binary labels with unary costs and pairwise “different labels” costs	min $s$–$t$ cut (submodular energies)
many edges from a vertex to a range of vertices	segment-tree helper nodes (Range Graph)
maximise ratio (edges / vertices)	parametric cut + Dinkelbach (densest subgraph)
sports elimination (can team $x$ still win?)	games as nodes with capacity = games left, teams capped at $W_x-w_i$

Lower bounds and circulations

Edge $(u,v)$ with $\ell \le f\le c$: send $\ell$ unconditionally (it adds $\ell$ to $v$‘s excess and removes it from $u$‘s), keep a residual edge of capacity $c-\ell$. Connect positive-excess vertices from a super-source $S$ and negative-excess vertices to a super-sink $T$; a feasible circulation exists iff the max flow saturates all of $S$‘s edges. For an $s$–$t$ flow with lower bounds add $t\to s$ with infinite capacity first; for the maximum such flow, then remove that edge and augment $s\to t$; for the minimum, augment $t\to s$ and subtract.

struct LowerBoundFlow {
    int n; Dinic D; vector<ll> exc; vector<int> ids; vector<ll> lo;
    LowerBoundFlow(int n) : n(n), D(n + 2), exc(n) {}
    int addEdge(int u, int v, ll l, ll c) { exc[v] += l; exc[u] -= l; ids.push_back(D.addEdge(u, v, c - l)); lo.push_back(l); return sz(ids) - 1; }
    bool circulate() {                                       // feasible circulation?
        int S = n, T = n + 1; ll need = 0;
        for (int v = 0; v < n; v++) { if (exc[v] > 0) D.addEdge(S, v, exc[v]), need += exc[v]; else if (exc[v] < 0) D.addEdge(v, T, -exc[v]); }
        return D.maxflow(S, T) == need;
    }
    ll solve(int s, int t, bool mx) {                         // LLONG_MIN if infeasible; call once
        int id = D.addEdge(t, s, LLONG_MAX / 4, LLONG_MAX / 4); // both ways: the value may be negative
        if (!circulate()) return LLONG_MIN;
        ll base = D.flowOn(id); D.e[id].cap = D.e[id ^ 1].cap = 0;
        return mx ? base + D.maxflow(s, t) : base - D.maxflow(t, s);
    }
    ll maxFlow(int s, int t) { return solve(s, t, true); }
    ll minFlow(int s, int t) { return solve(s, t, false); }
    ll flow(int i) const { return lo[i] + D.flowOn(ids[i]); }
};

Classic uses: matrix rounding (round every entry up or down keeping row and column sums rounded: rows $\to$ cells $\to$ columns with $[\lfloor a\rfloor ,\lceil a\rceil ]$; always feasible), “each road used at least once” covers, staffing with minimum requirements, and minimum flow problems such as the minimum number of paths covering all edges of a DAG (lower bound 1 on every edge).

Where a lower bound shows up	Meaning
”Every task must be done at least once”	$\ell =1$ on the task edge
”Each machine runs at least $k$ hours”	$\ell =k$
Chinese postman / route covering every road	$\ell =1$ per road
Scheduling with minimum staffing per shift	$\ell =$ required staff
Flow decomposition into exactly $k$ paths	lower bound $k$ on the source edge

Combine with min-cost flow when the lower bounds carry a cost too: after the same transformation, run MCMF instead of max flow, and add back the mandatory $\sum \ell \cdot \text{cost}$ at the end; negative edge costs then need Bellman–Ford potentials or an initial negative-cycle cancellation before the usual successive-shortest-paths loop.

Proof: the lower-bound reduction

Write $f=\ell +f^{\prime }$ with $0\le f^{\prime }\le c-\ell$. Conservation of $f$ at $v$ is ${\sum }_{\text{in}}{f}^{\prime }-{\sum }_{\text{out}}{f}^{\prime }=-\text{exc}(v)$ with $\text{exc}(v)={\sum }_{\text{in}}\ell -{\sum }_{\text{out}}\ell$. A flow $f^{\prime }$ with these imbalances is exactly an $S$–$T$ flow saturating the edges $S\to v$ (capacity $\text{exc}(v)>0$) and $v\to T$ (capacity $-\text{exc}(v)$), since ${\sum }_v\text{exc}(v)=0$ makes “saturate all $S$ edges” equivalent to “saturate all $T$ edges”. For the max $s$–$t$ flow: the circulation found with the $t\to s$ edge carries some $s$–$t$ value $b$; deleting that edge, any further $s$–$t$ augmentation in the residual graph keeps all lower bounds (residual capacities are relative to $\ell$) and the auxiliary $S,T$ are dead ends, so the maximum is $b$ plus the max flow in the residual network, by the standard augmenting-path optimality argument.

Maximum weight closure (project selection)

Choose a set closed under implications $u\Rightarrow v$ maximising total weight: $s\to v$ with capacity $w_v$ for $w_v>0$, $v\to t$ with $-w_v$ for $w_v<0$, $u\to v$ with $\infty$ for each implication. Answer $={\sum }_{w>0}w-\text{mincut}$, and the source side is an optimal set.

pair<ll, vector<bool>> maxClosure(const vector<ll>& w, const vector<pair<int, int>>& imp) {   // u => v
    int n = sz(w), s = n, t = n + 1; Dinic D(n + 2); ll pos = 0, INF = 0;
    for (ll x : w) INF += llabs(x);
    INF++;
    for (int v = 0; v < n; v++) { if (w[v] > 0) D.addEdge(s, v, w[v]), pos += w[v]; else if (w[v] < 0) D.addEdge(v, t, -w[v]); }
    for (auto [u, v] : imp) D.addEdge(u, v, INF);
    ll cut = D.maxflow(s, t); vector<bool> ch(n);
    for (int v = 0; v < n; v++) ch[v] = D.sourceSide(v);
    return {pos - cut, ch};
}

Proof: finite cuts are closures

A cut $(S\cup \{s\},T\cup \{t\})$ has finite capacity iff no implication edge goes from $S$ to $T$, i.e. iff $S$ is closed. Its capacity is ${\sum }_{v\in T,w_v>0}{w}_v+{\sum }_{v\in S,w_v<0}(-w_v)={\sum }_{w>0}w-\text{weight}(S)$. Minimising the cut maximises the weight of the closure.

Binary labelling (submodular): cost $a_v$ if $v$ gets label 0, $b_v$ if label 1, and $c_{uv}\ge 0$ if $u,v$ get different labels: edges $s\to v$ ($b_v$), $v\to t$ ($a_v$), $u\leftrightarrow v$ ($c_{uv}$); label 0 = source side. Penalties for ”$u=1$ and $v=0$” only become a single directed edge $u\to v$. Non-submodular terms (rewarding different labels) can be handled on bipartite structures by flipping one side’s labels.

Densest subgraph

Maximise $|E(S)|/|S|$. For a guess $g=p/q$, the network $s\to v$ ($qm$), $v\to t$ ($qm+2p-q\mathrm{deg}v$), $u\leftrightarrow v$ ($q$) has min cut $qmn+2{\min }_S(p|S|-q|E(S)|)$, so a cut below $qmn$ certifies a denser set (the source side). Dinkelbach: start with $S=V$ and jump to the certified set until none exists; a few flows suffice, all in exact integers.

tuple<ll, ll, vector<int>> densestSubgraph(int n, const vector<pair<int, int>>& E) {   // density num/den and the set
    ll m = sz(E); if (!m) return {0, 1, {0}};
    vector<ll> deg(n); for (auto [u, v] : E) deg[u]++, deg[v]++;
    auto improve = [&](ll p, ll q, vector<int>& S) {
        int s = n, t = n + 1; Dinic D(n + 2);
        for (auto [u, v] : E) D.addEdge(u, v, q, q);
        for (int v = 0; v < n; v++) D.addEdge(s, v, q * m), D.addEdge(v, t, q * m + 2 * p - q * deg[v]);
        ll cut = D.maxflow(s, t); S.clear();
        for (int v = 0; v < n; v++) if (D.sourceSide(v)) S.push_back(v);
        return cut < q * m * n;
    };
    vector<int> best(n), S; iota(all(best), 0); ll num = m, den = n;
    while (improve(num, den, S)) {
        vector<char> in(n); for (int v : S) in[v] = 1;
        ll e = 0; for (auto [u, v] : E) e += in[u] && in[v];
        num = e, den = sz(S), best = S;
    }
    ll g = gcd(num, den); return {num / g, den / g, best};
}

Proof: Goldberg's construction

For a source set $S$ (excluding $s$), the cut capacity is $qm(n-|S|)+{\sum }_{v\in S}(qm+2p-q\mathrm{deg}v)+q\cdot e(S,\bar{S})$. Using ${\sum }_{v\in S}\mathrm{deg}v=2|E(S)|+e(S,\bar{S})$, this simplifies to $qmn+2p|S|-2q|E(S)|$. So the min cut is below $qmn$ iff some nonempty $S$ has $q|E(S)|>p|S|$, i.e. density $>p/q$, and the minimising $S$ maximises $q|E(S)|-p|S|$. Dinkelbach’s iteration strictly increases the density each round and stops at the optimum; there are only finitely many density values.

Path covers and Dilworth

• Vertex-disjoint paths covering a DAG: split each vertex into ${\text{out}}_v$ (left) and ${\text{in}}_v$ (right), edge $u\to v$ becomes ${\text{out}}_u-{\text{in}}_v$; min paths $=n-$ max matching (each matched edge glues two path pieces).
• Paths may share vertices (chains): first take the transitive closure, then the same. By Dilworth, the minimum number of chains = maximum antichain; a maximum antichain is read off König’s vertex cover (vertices $v$ with neither ${\text{out}}_v$ nor ${\text{in}}_v$ in the cover).

vector<vector<int>> minPathCover(int n, const vector<pair<int, int>>& E) {   // vertex-disjoint paths of a DAG
    Dinic D(2 * n + 2); int s = 2 * n, t = s + 1; vector<int> ids;
    for (int v = 0; v < n; v++) D.addEdge(s, v, 1), D.addEdge(n + v, t, 1);
    for (auto [u, v] : E) ids.push_back(D.addEdge(u, n + v, 1));
    D.maxflow(s, t);
    vector<int> nxt(n, -1), hasPrev(n);
    for (int i = 0; i < sz(E); i++) if (D.flowOn(ids[i])) nxt[E[i].first] = E[i].second, hasPrev[E[i].second] = 1;
    vector<vector<int>> paths;
    for (int v = 0; v < n; v++) if (!hasPrev[v]) { paths.push_back({}); for (int x = v; x != -1; x = nxt[x]) paths.back().push_back(x); }
    return paths;
}

Proof: paths $=n-$ matching

In any set of vertex-disjoint paths covering the DAG, the path edges form a matching between out-copies and in-copies (each vertex has at most one successor and one predecessor on its path), and the number of paths is $n$ minus the number of path edges. Conversely a matching defines successor/predecessor pointers that form vertex-disjoint paths (no cycles, since the graph is a DAG). So minimising paths is maximising the matching.

Flow decomposition

Any flow decomposes into at most $E$ paths and cycles: repeatedly walk from $s$ along edges with positive flow; reaching $t$ closes a path, revisiting a vertex closes a cycle; subtract the bottleneck. Each extraction zeroes an edge. Used to output the actual routes (CSES Distinct Routes), and in proofs (integrality, path covers).

vector<pair<ll, vector<int>>> decompose(int n, int s, int t, vector<array<ll, 3>> fe) {   // {u, v, flow}; returns s-t paths (edge ids)
    vector<vector<int>> out(n); for (int i = 0; i < sz(fe); i++) out[fe[i][0]].push_back(i);
    vector<int> ptr(n); vector<pair<ll, vector<int>>> paths;
    auto nxt = [&](int u) { while (ptr[u] < sz(out[u]) && fe[out[u][ptr[u]]][2] <= 0) ptr[u]++; return ptr[u] < sz(out[u]) ? out[u][ptr[u]] : -1; };
    while (s != t && nxt(s) != -1) {
        vector<int> es, pos(n, -1), vs{s}; pos[s] = 0;
        while (vs.back() != t) {
            int e = nxt(vs.back()); if (e < 0) break;           // only happens if conservation fails
            int v = fe[e][1]; es.push_back(e);
            if (pos[v] >= 0) {                                  // cycle: cancel it and continue
                ll a = LLONG_MAX; for (int i = pos[v]; i < sz(es); i++) a = min(a, fe[es[i]][2]);
                for (int i = pos[v]; i < sz(es); i++) fe[es[i]][2] -= a;
                for (int i = pos[v] + 1; i < sz(vs); i++) pos[vs[i]] = -1;
                vs.resize(pos[v] + 1); es.resize(pos[v]); continue;
            }
            pos[v] = sz(vs); vs.push_back(v);
        }
        if (vs.back() != t) break;
        ll a = LLONG_MAX; for (int e : es) a = min(a, fe[e][2]);
        for (int e : es) fe[e][2] -= a;
        paths.push_back({a, es});
    }
    return paths;
}

Proof: decomposition exists and terminates

Conservation guarantees that from any vertex $\ne t$ reached by positive flow there is an outgoing edge with positive flow, so the walk either reaches $t$ or repeats a vertex. Subtracting the bottleneck along a path or cycle keeps conservation (each internal vertex loses the same amount in and out) and zeroes at least one edge, so there are at most $E$ extractions. The sum of the extracted path amounts equals the flow value since cycles carry no net $s$–$t$ flow.