Dinic
Algorithm for finding [maximum flow
Dinic is O(V^2E)
My Python implementation (verified by AOJ)
The edge is waiting in defaultdict(dict), so there is no need to have the index of the inverse side to get the inverse side.
(Many C++ implementations have an inverse index on each side.)
Do not search for previously explored edges.
This is achieved by having "the first index of the edge not yet explored" in the itertion_count.
To use this, we need a mapping from index to edges, so we make it first in max_flow: edges_index.
Implementation of others
---
This page is auto-translated from /nishio/Dinic using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.