hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 最小費用流 Min Cost Flow 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいかも) アルゴリズムは2つあるっぽく、制約が厳しいときは使い分けないといけないかも（不確定な情報） 1. O(V^2UC)のやつ -> 辺の数が多いときはこっち 実装 2. O(fElogV)のやつ -> 費用が大きいときはこっち 実装 ネットワーク単体法が最速アルゴリズムらしいが、今まで上の2つで通らなかった問題はみたことがない こういう発展… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F05%2F09%2F120428" title="競技プログラミングにおける最小費用流問題まとめ - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-05-09 12:04:28 rich https://blog.hamayanhamayan.com/entry/2017/05/09/120428 1.0 100%