恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ 最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何?)ので頑張って通すと良さそう。 Minimum cost b-flow フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました ぼくの考えたさいきょうのフローライブラリ - みさわめも みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。 b-flow というのは、各頂点に需