最小費用流の負辺除去

つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。
この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。

最小費用流への認識

最小費用流を最大流みたいに「始点 S から終点 T に水を流す」という問題だと思っていたならそれは本質から少しずれています。(定義上は多分それで合ってると思いますが)
水の例えを用いつつより本質を付いた言い方をするならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。
つまり始点も終点も複数存在するという形がより本質に近いということです。
もっと言うと、始点と終点の区別もそんなにはっきりさせない方がいいでしょう。

もう少し具体的に変数を交えて書くとこんな感じです。

  • 有向グラフがある
  • 最初、頂点には余っている水の量 d_v が定まっている
    • d_v が負なら不足していることを表している
    • 全体でみると過不足はない ( \sum d_v = 0 )
  • 辺には容量 cap_e とコスト cost_e が定まっている
  • u \to v を使うと、u から v に水を移すことができる
    • 移す量を x とすると、0 \leq x \leq cap_e を満たさなければならず、コストは x \cdot cost_e 掛かる
  • 過不足を解消するための最小コストは?

最初から過不足がない場合は最小費用循環流問題ってやつになります。
負辺がある場合、わざわざサイクルに水を流してコストを減らすこともある点に注意。

負辺除去

本題です。
負辺がある場合は、最初に逆向きに流しておいて、コストが正の逆向きの辺があったとみなすだけで良いです。
負辺 u \to v が来たときに具体的にやる操作を書くと、こんな感じです。

  • d_u から cap_e を引き、d_vcap_e を足す
  • 答えに cost_e \cdot cap_e を足しておく
  • 容量 cap_e コスト -cost_e の辺 v→u を追加する

かなり自然じゃない?

実装

蟻本方式の実装でやるなら、超頂点 S', T' を用意して、

  • d_v が正:S' から v へ容量 d_v コスト 0 の辺を張る
  • d_v が負:v から T' へ容量 -d_v コスト 0 の辺を張る

で正の d_v の和だけ流せば良いです。
実装をいじれば超頂点を作らなくてもできると思います。
あと、cost scalingってやつもおすすめらしいのでそのうち書くかも。(流量が大きくなりがちなこの手法と相性が良さそう)

おまけ

上の定式化そのままではないケースへの対処法あれこれ

  • SからTに流すんだけど流量が自由な場合
    • T→Sに容量INFコスト0の辺を張るだけ
  • SからTに流すんだけど流せるだけ流さないといけない場合
    • T→Sに容量INFコスト-INFの辺を張っておいて後で答えからこの辺のコストを引く
  • 最小流量付きの辺がある場合
    • 負辺除去と同じノリであらかじめ最小流量だけ流しておけば良い

補足

負辺除去には他の方法もあるので、それらを比較したwata先生のツイートを引用させていただきます。(ありがとうございます)

  • Bellman-Fordでポテンシャル初期化(負の閉路無し) O(F m log n + nm).
  • 適当に定数足して非負に (大きさFの最大重み二部マッチングなど) O(F m log n).
  • 逆向きに流して負辺除去 O((F+F') m log n), F'は負の辺の容量の和.

ちなみにこれらは3つとも蟻本に載っています。
シチュエーションに合わせて別の手法を選んだ方が良いこともあるかもしれません。
(特に2つ目は実装楽だし早いしよく出てくるし便利)