最小費用流についてのちょっとしたメモ

恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ

最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何？)ので頑張って通すと良さそう。 Minimum cost b-flow

フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました
ぼくの考えたさいきょうのフローライブラリ - みさわめも
みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。

b-flow というのは、各頂点に需給が設定されており、各頂点周りで辺の流量のin/outのバランスがbとなっているものである。(組合せ最適化においてもこの定式化)

これをよく見るs-tフローの形にするには、b(v)>0なるvたちにはs->vに容量b(v)の辺を張り、b(v)<0なるvたちにはv->tに容量-b(v)の辺を張って、s->tにbが正のものの和だけ流せばよい。

最短路問題のようなものを考える場合でも、負の閉路があるかどうかというのが重要で、ないものは保守的(組合せ最適化より)と呼ばれ、そのような場合実行可能ポテンシャルが取れる。 (負の閉路が無いことと同値である) 保守的である場合、例えば Bellman-Ford などで適当にやると実行可能ポテンシャルの1つが取れる。

最小費用流においても残余グラフにおいて負の費用の閉路がないことが最適性を特徴付けるのだが、SSP(蟻本もこれだっけ)のアルゴリズムでは各ステップであるb'があって最適なb'-flow、となる形で流量を保持しつつ、この実行可能ポテンシャルも同時に保持しているということがある(これもあまりわかってなかった) このアルゴリズムでは、cだと負辺がある場合もあるが、前のステップのポテンシャルを用いて簡約距離 (x->yに重みwの辺があるときh(x)+w-h(y) みたいな量、ポテンシャルになってればこれは非負)についての最短距離を求めても同じであることを利用して Dijkstra を使える形にしている (天才)

ちなみに、最小費用流の双対LPを見ると実行可能ポテンシャルですね〜という形をしていて、SSPで得られるポテンシャルが双対問題の解にもなっています。

負の辺があると...怖い！というのは有名なはずだがあまり対処方法は有名でないような。結論から言えば、負のコスト(かつ容量正)の辺を逆に全部使ってしまったことにしてbの値を調整し、逆辺があったことにすると残余グラフが保守的であることにできます。あとは1回Bellman-Fordした後はDijkstraでできます。SSPの計算量は|b(v)|の値に依存してるので計算量に注意が必要ではあります。

これは、上で述べたように、1回ポテンシャルの形にできてしまえば後は非負のままできるというわけで、何もしなくても保守的なグラフであれば、すべての容量が0でもbが0ベクトルのときのb-flowの形になってるので初めのポテンシャルを求めてあげればいいわけです。

容量下限がある場合にも、下駄をはかせたりして解決しがちですが問答無用で下限分だけ使ってbを調整した後上限-下限の辺があることにしてオラクルを呼べばいいです。これも計算量に注意 (misawaさんの記事には逆辺の上限を弄る方法が紹介されていて、天才)

なお、yosupo judgeのはbがでかいので scaling 系とかをやらないと通りません。やりおるわ