<ul>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E6%B5%81">最大流</a>を求めるアルゴリズム<ul>
<li>DinicはO(V^2E)</li>
</ul>
</li>
<li><a href="/ja/%E6%9C%80%E5%A4%A7%E6%B5%81%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%AD%B4%E5%8F%B2">最大流を求めるアルゴリズムの歴史</a></li>
<li><a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp">AOJ GRL_6_A 最大流</a>で実装の検証ができる</li>
<li>僕のPython実装(AOJで検証済み)<ul>
<li>辺はdefaultdict(dict)で待ってるので逆辺の取得のために逆辺のindexを持つ必要はない<ul>
<li>(多くのC++実装では各辺に逆辺のindexを持たせてる)</li>
</ul>
</li>
<li>「探索済み辺を探索しない」<ul>
<li>これを「まだ探索してない辺の最初のindex」を<code>itertion_count</code>に持つことで実現している</li>
<li>これを使うためにはindexから辺への対応づけが必要だから<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>
<p>他の人の実装</p>
<ul>
<li><a href="/ja/%E8%9F%BB%E6%9C%AC">蟻本</a>　p.194</li>
<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>
</ul>
<p><a href="/ja/%E6%9C%80%E5%A4%A7%E4%BA%8C%E9%83%A8%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0">最大二部マッチング</a></p>
