最小費用流の負辺除去

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

追記 (2021-08-15):
ポテンシャルを求めるのが簡単な場合にはそれを使って負辺除去する方が楽です。
この記事の方法はグラフが複雑だったり、思考停止したいとき用かなぁ。
例題

最小費用流への認識

最小費用流は「始点 S から終点 T に水を流す」という問題に見えがちですが、それは少し本質とずれています。
水の例えを用いつつ言うならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。
実装の際に始点と終点があった方が分かりやすいことがあるだけで、定義上は必要なものではないんですね。

具体的に変数を使って書くとこんな感じです。(←最小費用流とかのLPの定式化とか見るとさらに分かりやすい)

  • 有向グラフがある
  • 最初、頂点には余っている水の量 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 掛かる
  • 過不足を解消するための最小コストは?

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

負辺除去

本題です。
負辺がある場合は、最初にmaxまで流しておいて、コストが正の逆向きの辺があったとみなすだけで良いです。
負辺 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)
    (右側の頂点たちにXのポテンシャルを付けているとも見なせる)
  • 予めmaxまで流して負辺除去 O((F+F') m log n), F'は負の辺の容量の和

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

関連記事:最小費用流の負辺除去・最小流量制限 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ