Pattern 1: Maximum-Weight Closure (Project Selection) via $s$-$t$ Min-Cut
Suppose you have $N$ projects where project $i$ yields net value $w_i \in \mathbb{R}$ ($w_i > 0$ for profitable projects, $w_i < 0$ for prerequisite infrastructure/machines), and a dependency DAG where choosing $u$ requires also choosing $v$ ($u \to v$). A valid selection $A \subseteq V$ is a closure (no edge leaves $A$).
Construct a flow network on $V \cup \{s, t\}$:
- For each profitable node $u$ with $w_u > 0$, add edge $(s, u)$ with capacity $w_u$.
- For each costly node $v$ with $w_v < 0$, add edge $(v, t)$ with capacity $|w_v| = -w_v$.
- For each prerequisite dependency $u \to v$, add edge $(u, v)$ with capacity $\infty$.
For any finite-capacity cut $(S, T)$, no $\infty$ edge can cross from $S$ to $T$, so $A = S \setminus \{s\}$ is a valid closure! Its cut capacity is:
$$c(S, T) = \sum_{u \in T, w_u > 0} w_u + \sum_{v \in S, w_v < 0} |w_v| = \underbrace{\sum_{w_u > 0} w_u}_{W^+} - \sum_{u \in A} w_u$$Therefore, minimizing $c(S, T)$ maximizes $\sum_{u \in A} w_u = W^+ - \text{MinCut}(s, t)$! $\blacksquare$
Model Max-Weight Closure (Project Selection) as S-T Min-Cut with ∞ prerequisite arcs, tighten Hungarian dual potentials u_i + v_j = c_ij on the equality subgraph, or route Min-Cost Max-Flow via Johnson reduced costs.
Invariant & State
Pattern 2: Flow with Edge Lower Bounds $L(e) \le f(e) \le U(e)$
What if every edge $e = (u, v)$ requires at least $L(e)$ units of flow: $L(e) \le f(e) \le U(e)$? Write $f(e) = L(e) + f'(e)$ where $0 \le f'(e) \le U(e) - L(e)$. Pre-committing $L(e)$ creates a vertex net balance $b(v) = \sum_{e \in \text{in}(v)} L(e) - \sum_{e \in \text{out}(v)} L(e)$ that $f'$ must absorb:
- Add a super-source $S^*$ and super-sink $T^*$.
- For each vertex $v$ with $b(v) > 0$ (excess incoming lower-bound flow), add edge $(S^*, v)$ of capacity $b(v)$.
- For each vertex $v$ with $b(v) < 0$ (deficit), add edge $(v, T^*)$ of capacity $-b(v)$.
- For an $s$-$t$ flow network (not a closed circulation), add a feedback edge $(t, s)$ with capacity $\infty$.
A feasible circulation exists if and only if $\text{MaxFlow}(S^*, T^*) = \sum_{b(v) > 0} b(v)$ (saturating all outgoing edges from $S^*$)!
Standard flow networks only constrain edge capacities. Whenever a vertex $u$ can pass at most $C_u$ units of flow (or in vertex-disjoint paths / minimum vertex cut), split $u$ into two nodes $u_{\text{in}} = 2u$ and $u_{\text{out}} = 2u + 1$ connected by an internal directed edge $(u_{\text{in}}, u_{\text{out}})$ of capacity $C_u$, routing all incoming edges into $u_{\text{in}}$ and all outgoing edges from $u_{\text{out}}$.
| Modeling Problem | Graph Construction | Objective Formula |
|---|---|---|
| Project Selection (Max Closure) | $s \xrightarrow{w_u} u \xrightarrow{\infty} v \xrightarrow{|w_v|} t$ | $\sum_{w_u > 0} w_u - \text{MaxFlow}(s, t)$ |
| Vertex Capacity $C_u$ | Split $u \mapsto u_{\text{in}} \xrightarrow{C_u} u_{\text{out}}$ | Standard Max-Flow / Min-Cut on $2V$ nodes |
| Lower-Bound Circulation | Cap $U(e)-L(e)$; connect $S^* \to v$ ($b_v > 0$), $v \to T^*$ ($b_v < 0$) | Feasible iff $\text{MaxFlow}(S^*, T^*) == \sum_{b_v > 0} b_v$ |
| Bipartite Min Weight Vertex Cover | $s \xrightarrow{w_u} u \in L$, $u \xrightarrow{\infty} v$, $v \in R \xrightarrow{w_v} t$ | $\text{MinCut}(s, t) = \text{MaxFlow}(s, t)$ |
Production C++20 Implementation: Maximum-Weight Closure (Project Selection) Solver
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
struct ClosureResult {
long long maxNetProfit;
std::vector<int> selectedProjects;
};
// weights[i] > 0: profit of project i; weights[i] < 0: cost of prerequisite i
// dependencies: pairs (u, v) meaning selecting u requires selecting v
ClosureResult solveMaxWeightClosure(
const std::vector<long long>& weights,
const std::vector<std::pair<int, int>>& dependencies) {
int n = static_cast<int>(weights.size());
int s = n, t = n + 1;
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
Dinic dinic(n + 2);
long long totalPositiveProfit = 0;
for (int i = 0; i < n; ++i) {
if (weights[i] > 0) {
totalPositiveProfit += weights[i];
dinic.addEdge(s, i, weights[i]);
} else if (weights[i] < 0) {
dinic.addEdge(i, t, -weights[i]);
}
}
for (auto [u, v] : dependencies) {
dinic.addEdge(u, v, INF);
}
long long minCutLoss = dinic.maxFlow(s, t);
// Selected projects are vertices in S (reachable from s in final residual graph)
// Note: in our Dinic class, final BFS sets level[u] != -1 iff u is reachable from s in G_f!
return {totalPositiveProfit - minCutLoss, {}};
}LLONG_MAX for $\infty$ Edges (Integer Overflow)When modeling hard constraints with $\infty$ edges, never use std::numeric_limits<long long>::max() directly if your flow solver or cut summation ever adds two capacities together. Set INF to strictly exceed $\sum_{w_u > 0} w_u + 1$ (e.g., 1e15), which guarantees no min-cut can ever sever a hard dependency edge while preventing 64-bit integer overflow.