---
# System prepended metadata

title: Max Flow

---

Ford fulkersson augmenting

edmond

https://cses.fi/problemset/task/1711

# flow

torn bipartit matchning (finns inte)

[unfairplay](https://open.kattis.com/problems/unfairplay)

cow problem [floodingfields](https://open.kattis.com/problems/floodingfields)

[kaguya wa saketakunai](https://open.kattis.com/problems/kaguyawasaketakunai)

## cyclic partitioning
partition graph into node disjoint cycles

partition graph to maximize number of nodes in cycles (LP)

## lower bound flow

[escape routes](https://open.kattis.com/problems/escaperoutes)

# min cut

https://codeforces.com/blog/entry/136761

remove min edges no path

split into two sets, source in first, target in second. pay penalty all edges a to b

- $S_i = 0$ cost $A_i$
- $S_i = 1$ cost $B_i$
- $S_i = 1, S_j=0$ cost $C_{i,j}$



[landscaping](https://open.kattis.com/problems/landscaping)

[arc085c](https://atcoder.jp/contests/arc085/tasks/arc085_c)

[open-pit mining](https://open.kattis.com/problems/openpitmining)

# MCMF

[tourist](https://open.kattis.com/problems/tourist)

[castle building](https://chalmerschallenge25.kattis.com/contests/chalmerschallenge25/problems/castlebuilding)

[excitingtournament](https://open.kattis.com/problems/excitingtournament)

# augmenting path

[fake scoreboard](https://open.kattis.com/problems/fakescoreboard)
