modeling problems as network flow
The real power of flow theory is rarely the flow itself — it is that a problem with no obvious pipes in it can be reshaped into a network so that its maximum flow or minimum cut is the answer you wanted all along. Learning to spot when 'choose a best subset' or 'separate two groups cheaply' is secretly a flow problem is one of the most leveraged skills in algorithm design.
The craft is a small kit of gadgets. Bipartite matching: source to left (cap 1), left to right on allowed pairs, right to sink (cap 1); max flow is the largest matching. Vertex capacities: split a vertex v into v-in and v-out joined by an edge whose capacity is v's limit, so a node can carry only so much. Lower bounds or 'must use' edges: shift flow with auxiliary source/sink edges. Two large families are especially common. Project selection / maximum-weight closure: you may take a project only if its prerequisites are taken; model profits as source edges, costs as sink edges, prerequisites as infinite-capacity edges, and the minimum cut splits 'take' from 'leave' to maximize net profit. Image segmentation: pixels are vertices, neighbor pairs are edges whose capacity is the penalty for separating them, source and sink are the two labels, and the minimum cut is the cheapest foreground/background boundary. Edge-disjoint paths: give every edge capacity 1, and the max flow equals the maximum number of edge-disjoint s-t paths (Menger's theorem).
Done well, modeling-as-flow turns problems that look like they need brute force or clever ad hoc reasoning into a polynomial call to a max-flow or min-cut routine, often with a duality certificate explaining the optimum. The discipline that keeps it honest: after building the network, you must prove the correspondence both ways — every valid solution to your problem maps to a flow/cut of equal value, and every integer flow/cut maps back to a valid solution — otherwise the construction may quietly answer a different question. And know the boundary: many problems genuinely do NOT reduce to flow (general matching needs blossoms; problems with conflicting either-or constraints can be NP-hard), so flow is a powerful default to try, not a universal hammer.
Project selection: projects with profits +10, +4 and a shared tool costing -6 that both need. Source -> each profit (cap = profit), tool -> sink (cap = cost), each project -> tool (cap = infinity, enforcing 'need the tool'). The min cut equals total profit minus the best net selection; here taking both projects and paying for the tool nets 10 + 4 - 6 = 8, which the cut recovers.
A minimum cut partitions items into take/leave to maximize net value — the gadget encodes the constraints as infinite-capacity edges.
A flow model is only as good as its proof of correspondence. Always verify that every problem solution corresponds to a flow/cut of equal value and vice versa; and remember not everything reduces to flow — general matching, and many either-or constraint problems, do not.