Graphs -> Min-Cost Flow

Successive shortest augmenting paths, potentials, and reduced costs for transportation-style optimization.

• Topic slug: graphs/min-cost-flow
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 0
• Curated external problems: 10

Microtopics

• potentials
• reduced-cost
• successive-shortest-path
• negative-cycle
• assignment
• circulation

Learning Sources

Source	Type
MIT 6.854 min-cost flow notes	Course
cp-algorithms min-cost flow	Reference
USACO Guide min-cost flow	Reference

Practice Sources

Source	Type
Library Checker min_cost_b_flow	Practice
CSES Problem Set	Practice
USACO contest archive	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Crime Wave - The Sequel	UVa	Medium	Min-Cost Max-Flow, Assignment	Assignment Model; Min-Cost Matching	Bipartite Matching; Shortest Augmenting Path	Bipartite Matching	A classic costed matching problem on a bipartite graph.
Minimum Cost Flow	AOJ	Medium	-	-	-	Min-Cost Max-Flow; Potentials; Shortest Augmenting Path	Official min-cost-flow baseline.
Distinct Routes II	CSES	Hard	-	-	-	K Routes; Path Reconstruction	A direct cost-minimization variant over route decompositions.
Parcel Delivery	CSES	Hard	-	-	-	Capacitated Edges; Transport	Natural costed transport network formulation.
Task Assignment	CSES	Hard	-	-	-	Assignment; Bipartite Matching; Cost Matrix	Classic assignment problem, often solved as min-cost flow.

Classics

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Another Assignment Problem	SPOJ	Medium	Assignment	Costed Bipartite Matching; Successive Shortest Augmenting Path	Bipartite Matching; Costed Residual Graphs	Matching	Direct minimum-cost assignment, ideal for MCMF practice.

Advanced

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Data Flow	UVa	Hard	Capacity Planning	Binary Search Over Time; Min-Cost Flow Feasibility	Capacity Constraints; Cost-Aware Flow	Latency; Throughput	Blends feasibility, capacity, and path cost into one MCMF model.
Dijkstra, Dijkstra.	UVa	Hard	Min-Cost Max-Flow, Disjoint Paths	Successive Shortest Augmenting Path	Shortest Path On Residual Graph; Potentials	Shortest Path	Classic two-disjoint-paths min-cost-flow problem.
Yet Another Assignment Problem	SPOJ	Hard	Scheduling	Time-Expanded Scheduling; Cost Minimization	Min-Cost Flow Modeling; Job Assignment	Assignment	Scheduling with costs and capacities is a richer MCMF variant.

Cross-Topic

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Warehouse	UVa	Hard	Grid Modeling	Graph Construction From Grid; Minimum Cost Assignment	Shortest Path Distances; Min-Cost Matching	Grid; Movement Cost	Grid movement costs map neatly to min-cost assignment.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
MINCOST	Luồng với chi phí nhỏ nhất	secondary	hard	transportation network; flow reconstruction; duplicate-edge overwrite	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py