<pre><code>- Algorithm for finding [maximum flow
- Dinic is O(V^2E)
- [History of Algorithms for Maximum Flow](/en/History%20of%20Algorithms%20for%20Maximum%20Flow)
</code></pre>
<ul>
<li><a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp">AOJ GRL_6_A Maximum Flow</a> to verify implementation.</li>
<li>My Python implementation (verified by AOJ)<ul>
<li>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.<ul>
<li>(Many C++ implementations have an inverse index on each side.)</li>
</ul>
</li>
<li>Do not search for previously explored edges.<ul>
<li>This is achieved by having &quot;the first index of the edge not yet explored&quot; in the <code>itertion_count</code>.</li>
<li>To use this, we need a mapping from index to edges, so we make it first in <code>max_flow</code>: <code>edges_index</code>.</li>
</ul>
</li>
</ul>
</li>
<li><a href="https://github.com/nishio/atcoder/blob/master/libs/dinic_maxflow.py">GitHub</a></li>
</ul>
Implementation of others
 - <a href="/en/anthology">anthology</a> 　p.194
<ul>
<li><a href="http://algoogle.hadrori.jp/algorithm/dinic.html">http://algoogle.hadrori.jp/algorithm/dinic.html</a>
</li>
<li><a href="https://ei1333.github.io/luzhiled/snippets/graph/dinic.html">https://ei1333.github.io/luzhiled/snippets/graph/dinic.html</a>
</li>
<li><a href="https://tubo28.me/compprog/algorithm/dinic/">https://tubo28.me/compprog/algorithm/dinic/</a>
</li>
<li><a href="http://www.prefield.com/algorithm/graph/dinic.html">http://www.prefield.com/algorithm/graph/dinic.html</a>
</li>
<li><a href="/en/Maximum%20two-part%20matching">Maximum two-part matching</a>
</li>
</ul>
<hr>
This page is auto-translated from <a href="https://scrapbox.io/nishio/Dinic">/nishio/Dinic</a> 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 <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.