最小費用流 Min Cost Flow 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいか…

最大マッチング 色々な種類のマッチング問題があるが、大体調べれば多項式時間で解けるアルゴリズムがでてくる 二部最大マッチング 最大流問題に帰着できる（O(V^2E)かO(E*maxflow)） 二部グラフの最大マッチング＝最小頂点被覆 問題 二部グラフの被覆問題は…

最大流 Max flow 有向グラフで各辺ごとに流せる水の量が決まっていて、始点から終点まで最大どれだけの量流せるかを判定する 参考1 参考2 参考3 Dinic法はO(V^2E)、フォード・ファルカーソンではO(E*maxflow) 最大流を応用すると「二部マッチング」が解ける …