最小費用流
- Min Cost Flow
- 最大流の辺にコストがついたもので、ソースからシンクへある量のフローを流す時の各辺のフローとコストの積の総和を最小化する
- コストを損失と考えて最大化問題を解く考え方がよく使われる(こっちでそれを練習してからの方がいいかも)
- アルゴリズムは2つあるっぽく、制約が厳しいときは使い分けないといけないかも（不確定な情報）
1. O(V^2UC)のやつ -> 辺の数が多いときはこっち 実装
2. O(fElogV)のやつ -> 費用が大きいときはこっち 実装
- ネットワーク単体法が最速アルゴリズムらしいが、今まで上の2つで通らなかった問題はみたことがない
- こういう発展的話題もある
- 最小費用循環流というもある（ソースとシンクが無い最小費用流らしい、最小費用流に帰着できるらしい）
- コストが「個数^2」とか「2^個数」とかに成るやつは差分のコストを追加していくと表現できる 例題
問題
- AOJ 最小費用流
- ABC004 D.マーブル
- ABBYY Cup 3.0 C2. Tidying Up 解説
- Maximam Cup 2013 F.3人の騎士と1匹の犬 解説
- HackerRank Week of Code 32 Balls and Boxes
- Code festival 2014 上海 H. Dungeon 解説
- ECR29 Almost Permutation 解説
- ECR31 Anti-Palindromize
- HE Holi and Cultural Festival
- 2018 TCO Algorithm Round 2B Div1 Hard SquareFreeSet 解説
- SRM770 Div1 Med ShoppingSpree 解説
コストが実数
難しくてまだ通してない
