Found in
logistics
Articles
GRA
Algorithm
Dinic's algorithm
Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks.
O(V² E)
2 problems
GRA
Algorithm
Hungarian algorithm
Which job for whom at the least total cost: potentials, tight pairs and augmenting paths in O(n³).
O(n³)
2 problems
GRA
Algorithm
Eulerian path
Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E).
O(V + E)
3 problems
DP
Technique
Bitmask DP
The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile.
O(2ⁿ · n²) for the travelling salesman
2 problems
Problems
Often together
classic 4 contests 3 maps and navigation 3 matching 2 graph 2 optimization 2 dynamic programming 2 flows 1 connectivity 1 networks 1 matrix 1 weighted graph 1