Rare
0/5
Maximum Flow
Author: Benjamin Qi
Prerequisites
Introduces maximum flow as well as flow with lower bounds.
| Status | Source | Problem Name | Difficulty | Tags | Solution |
|---|---|---|---|---|---|
| CSES | Easy | Show TagsMax Flow | View Solution |
Resources
| Resources | |||
|---|---|---|---|
| CPC | |||
| CPH | |||
| CP2 | |||
Flows
| Status | Source | Problem Name | Difficulty | Tags | Solution |
|---|---|---|---|---|---|
| CSES | Easy | Show TagsMax Flow | View Solution |
Bipartite Matching
| Status | Source | Problem Name | Difficulty | Tags | Solution |
|---|---|---|---|---|---|
| CSES | Easy | Show TagsMax Flow | View Solution |
Dinic's Algorithm
| Status | Source | Problem Name | Difficulty | Tags | Solution |
|---|---|---|---|---|---|
| SPOJ | Easy | View Solution | |||
| YS | Easy | View Solution |
Hopcroft-Karp Bipartite Matching?
Optional: Faster Flow
There exist faster flow algorithms such as Push-Relabel. Also see the following blog post:
However, the standard implementation of Dinic's is (almost) always fast enough on reasonable problems.
Implementation
| Resources | |||
|---|---|---|---|
| Benq | |||
Breaking Flows
When the constraints are too high ...
Module Progress:
Give Us Feedback on Maximum Flow!
Join the Discussion!
Feel free to voice your thoughts in the comments section.