Graphs -> Maximum Flow¶

Residual graphs, augmenting paths, and cut structure for max-flow and min-cut modeling.

Microtopics¶

Material	Type
Police Chase note	`anchor note`
Maximum Flow push-relabel note	`anchor note`
Push-Relabel hot sheet	`quick reference`
Graph cheatsheet	`quick reference`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Download Speed	`CSES`	`Medium`	-	Dinic; S-T Max Flow	Network Flow Basics; Residual Graph	Directed Graphs; S-T Cut; Max Flow; Capacity; Network Throughput	Clean source-sink max-flow application.
Maximum Flow	`AOJ`	`Medium`	-	-	-	Max Flow; Push-Relabel; Dinic; Network	Official max-flow baseline.
Police Chase	`CSES`	`Medium`	-	-	-	Min Cut; Max Flow; Edge Cut	Exact minimum cut with an output certificate.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fast Maximum Flow	`SPOJ`	`Medium`	Min Cut	Dinic; Residual Graph	Augmenting Paths; Capacity Residuals	Undirected Graphs; Capacity	The standard introductory max-flow/min-cut baseline.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Angry Programmer	`UVa`	`Hard`	Min Cut, Node Splitting	Node/Edge Splitting; Min Cut Modeling	Flow Modeling; Min Cut Interpretation	Vertex Cuts; Security Model	Combines vertex and edge cuts, which is the classic split-node flow pattern.
Distinct Routes	`CSES`	`Hard`	Path Decomposition	Unit-Capacity Flow; Path Extraction	Augmenting Paths; Route Decomposition	Route Packing; Max Flow; Edge-Disjoint Paths; Route Recovery	Transforms edge-disjoint paths into a flow problem.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
The Problem with the Problem Setter	`UVa`	`Medium`	Bipartite Flow	Bipartite Flow; Source-Sink Layering	Bipartite Modeling; Flow Conservation	Matching; Assignment	A classic bipartite flow reduction with multiple source groups.
Power Transmission	`UVa`	`Hard`	Node Splitting	Vertex Splitting; Capacity Constraints	Flow Modeling; Vertex Capacity To Edge Capacity	Vertex Capacities	Uses node capacities, so it is a textbook vertex-splitting model.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`FFLOW`	Fast Maximum Flow	`primary`	`medium`	maximum flow; undirected capacities; capacity scaling	Note	Code
`MAXIMUMFLOWPUSHRELABEL`	Maximum Flow	`primary`	`medium`	-	Note	Code
`MINCOST`	Luồng với chi phí nhỏ nhất	`primary`	`hard`	transportation network; flow reconstruction; duplicate-edge overwrite	Note	Code
`POLICECHASE`	Police Chase	`primary`	`medium`	unit capacity max flow; residual reachable cut; minimum edge cut certificate	Note	Code
`REACTORCOOLING`	Reactor Cooling	`primary`	`hard`	feasible circulation; lower bounds; flow reconstruction	Note	Code

python3 scripts/generate_problem_catalog.py