最大フロー最小カット定理で解けるAtCoder Beginner Contest 010 D問題。scipyのmaximum_flowを使ってPythonで解く
scipyが気に入ったので、scipyの別アルゴリズムで解ける問題を順次やっていきます。
atcoder.jp
Pythonコード
解説で説明されている実装を、キレイにscipyのmaximum_flowで実装しているn_knuuさんのコードがあったので、それを元に書く。
まぁ、ほぼ一緒だけど。
最大フロー最小カット定理から、グラフの最大フローが最小工作数と合致する。