最小費用流

• 競技プログラミングにおける最小費用流問題まとめ - はまやんはまやんはまやん
• ネットワークフロー - ferinの競プロ帳

水道管に見立てた有向グラフがあって、 各辺には「頂点 $u$ から $v$ まで水を上限 $cap$ リットル流せる。1リットル流すには $cost$ 円かかる」という $(u,v,cap,cost)$ が決まっている。

$S$ から $T$ まで $F$ リットルの水を流したいとき、最小コスト $C$ はいくら？

辺上の数字の意味: --cap/cost→

 Ⓢ--3/3→○--2/1→○    F=5 を流したい場合、
 │       │       │      →→↓と流す量が 2、コスト (3+1+2) x 2 = 12
10/5     8/6      10/2     →↓→と流す量が 1、コスト (3+6+9) x 1 = 18
 ↓       ↓       ↓      ↓→→と流す量が 2、コスト (5+5+9) x 2 = 38
 ○--5/5→○--6/9→Ⓣ    計68のコストがかかる

いろいろあるが、シンプルな解法の1つに最短路反復がある。

グラフの作り方自体は最大流とよく似ている。

• $(u,v,cap,cost)$ で表される辺を張るとき、同時に $(v,u,0,-cost)$ という逆向きの辺も張る

グラフを構築したら、最小コストを調べる。

1. $S$ から $cap \gt 0$ の辺だけを使って、$S→T$ を現時点で最も安く流せるパスを1つ見つける
   • そのパスに流せるだけ流す
   • パス上の辺の $cap$ の最小値がそこに流せる最大流量（$f$ とする）
2. 残り流量とコストを更新する
   • $F←F-f$
   • $C←C+f \times (パス上の辺のcostの和)$
3. グラフを更新する
   • パス上の全ての辺の $cap$ を、$f$ だけ減らす
   • その辺と同時に張った逆辺の $cap$ を、$f$ だけ増やす

このようにグラフを更新すると、「一旦流してみたけど、このパスをフルに使うと既定流量 $F$ 流せなくなることが後からわかったので一部流さなかったことにする」ことが表現できる。

1～3.の処理を $F=0$ になるまで繰り返すと、その時の $C$ が答え。

計算量は $O(FE \log{V})$、$F$ が流したい流量、$E,V$ がそれぞれグラフの辺数、頂点数。

見つかったパスに流せる流量 $f$ が毎回 $1$ など少ない値だけ、なんてことも理論上はありうるので、$F$ が計算量にかかってくる。

上記では大まかな流れを書いたが、いろいろ問題を最小費用流に当てはめるにあたって例外的な工夫というか、留意すべき点がある。

最小費用のパスを1つ見つけ流せるだけ流す、というアルゴリズムでは、辺の容量が非整数（特に無理数）だと、いつまでたっても増加路がなくならないグラフが作れてしまう。

• 最大フローと最小カット - アルゴリズム (翻訳)

$cost$ と $-cost$ の辺が同時に張られるため、グラフに負の辺は必ず存在する。
そんなグラフ上で最短経路を探索する必要がある。

何が困るかってDijkstraが使えなくなる。方法は主に2つある。

• Bellman-Fordなど負辺があってもよいアルゴリズムで毎回探索する
  • ○実装が簡単
  • ×遅くなる
• 後述の「ポテンシャル」を導入してDijkstraが使えるようにする
  • ○速さが保たれる
  • ×何故それでいいか、までの理解はちょっと大変
  • ○ライブラリとして使う分には実装はそこまで複雑では無い
  • これを導入したアルゴリズムを特に、Primal-Dual法というらしい

ポテンシャルは、最短経路探索を複数回行う際に、負辺を上手いこと解消する方法。

• ダイクストラとポテンシャルのはなし - niuez’s diary

（逆辺を除いた）最初のグラフに負辺が含まれなければ、最初の1回は普通にDijkstraを回せる。
Dijkstraで $S$ からの各頂点に対するコストをまず求める。これをポテンシャルとする。（頂点 $v$ のポテンシャルを $h_v$ とする）

2回目以降の経路探索から負辺が生じうるが、以下のようにコストを更新していく。

• 頂点 $u$ へのコスト $dist_u$ が確定して、辺 $(u, v, cap, cost)$ を使って $v$ への暫定コスト $dist_v$ を更新する際、
  • 通常
    • $dist_v \xleftarrow[\min]{} dist_u + cost$ とするところ、
  • ポテンシャル
    • $dist_v \xleftarrow[\min]{} dist_u + cost + h_u - h_v$ とする

こうするとあら不思議、負のコストが生じなくなった上で、最短路も正しく求まる。

頂点 $v$ のポテンシャル $h_v$ は1回のDijkstraごとに以下で更新できる。$dist_v$ はポテンシャルを含んだ値。

• $h_v←h_v+dist_{v}$

通常の最短経路探索なら途中で $T$ までたどり着いたらそこで打ち切ればよいが、 今回はポテンシャルの更新があるので、全頂点への距離が求まるまで（キューが空になるまで）流しきる必要がある。

どう対処するかは問題に依るが、経路探索が終わるたびに $S→T$ パスが存在するかチェックする必要がある。

ポテンシャルを導入すればDijkstraが使える、という話をしたが、 最初の1回目の経路探索は何らかの方法で求める必要がある。
最初から負辺があるとここで困る。

解消方法が複数ある。

• ①1回目のポテンシャルはDijkstra以外の方法で計算
• ②上手く下駄を履かせて負辺を無くす
• ③機械的に負辺を無くす処理を施す

• 参考
  • 最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
  • 負辺を含む最小費用流について(Attack the Moles) - sigma425のブログ

大体、こんな感じのフローチャートで選択すればいいか。

• 負閉路がある（発生しうる）
  • →③機械的な除去
• 初期ポテンシャルを計算可能な制約・グラフ構造
  • →①
• 上手い下駄の履かせ方が思いついた
  • →②
• どれにも当てはまらない
  • →③を試す
• TLEになった
  • →②を頑張る

負辺が含まれていても $S$ から各頂点への最短コストを求めたい。以下のいずれかを使う。

• Bellman-Ford
• DAG（非巡回）であることがわかっている場合は、その順にDP

ただし負閉路がある場合は上手くいかないので、別の方法を考える。

各辺に何らかの値を足してコストを正にする→最小費用流を求める→最後に答えから一定値を引く。

たとえば「どの $S→T$ 経路も、使われる辺数が $P$ 本と決まっている」場合、 全ての辺に固定値 $X$ を足して負辺を無くして、最後に答えから $F \times X \times P$ を引けばよい。

他にも上手くいく場合があるが、問題依存で、なかなか一般的な手続きが見つけづらい。

大まかには、負のコストというのはいわば「賞金」なので、 最初にもらえるだけもらったと仮定した後、 それをもらえなくなる行動（を表す辺）を「罰金」＝正のコストとする、と考える場合が多い。

少し最小費用流の捉え方を変化させる。

これを踏まえた上で、$cost$ が負である辺 $(u,v,cap,cost)$ があった場合、これを機械的に正の辺にするには、

• その辺単体に流せるだけ流したとして、$cap \times -cost$ をまず得ておく（最後に答えから引く）
• $D_u$ を $cap$ 減らす
• $D_v$ を $cap$ 増やす
• 初期グラフでは $(u,v,0,cost)$ と $(v,u,cap,-cost)$ の辺を張る

と上手くいく。

問題が複雑なときに有効な方法だが、 最小費用流の計算量には流量 $F$ がかかってくるのに対し、この方法は $F$ が大きく増加しうる点に注意。

流量が大きいような最大流問題を解くのに、「cost scaling」「容量スケーリング」という手法がある？

• 容量スケーリング法のすゝめ - みさわめも

辺 $i$ に流す流量によってコストが変化する場合。

• 最初の5リットルまでを1リットル流すコストは $cost_{i,1}～cost_{i,5}=2$
• 6～15リットルのコストは $cost_{i,6}～cost_{i,15}=5$
• 16リットル以上のコストは $cost_{i,16}～cost_{i,\infty}=10$

などが決まっているとする。

この時、「$x \lt y$ において $cost_{i,x} \le cost_{i,y}$」、 つまり少なく流す分ほどコストが小さい、という条件下で最小費用流のグラフに落とし込める。
（通常はまとめ買いほど安くなるので感覚的には逆だが）

同じ頂点間に辺を複数本張る。

• 最初の5リットル: 容量 $5$, コスト $2$
• 次の10リットル: 容量 $10$, コスト $5$
• それ以降: 容量 $\infty$, コスト $10$

コストの少ない方から使われるので、問題なく答えが求められる。

• 適用できるケース①
  • 各辺に宝があり、最初に通った時のみ回収できる
• 適用できるケース②
  • 辺を使った回数毎に（1単位ずつではなく）全体でコストが定まっている
  • ex) 特定の辺を1回使ったらコスト $c_1$、2回使ったら $c_2$、……
  • 差分が条件を満たしていればいい。$c_1 \le c_2-c_1 \le c_3-c_2 \le ...$

辺だけで無く、頂点にも容量やコストが定まっている場合、頂点を2倍にすればよい。

    ↘  ↗
... →ⓥ→ ...    ⓥを通過できる容量は全体で10
    ↗            ⓥを通過した際のコストは1単位あたり6


    ↘      ↗
... →v1→v2→ ...   v1-v2間の辺に、
    ↗               その容量とコストを当てはめる

（本来のグラフでの）辺を張るとき、vに入る辺はv1に、vから出る辺はv2に接続する。

最大流問題を解くDinic法でも繰り返し $S→T$ パスを見つけるのだが、

• まずBFSで、始点からの各頂点への距離（辿る辺数）を「レベル」として算出
• 続くDFSでは、探索範囲をレベルが増える方向のみに限定する

BFS → DFSを繰り返す → Tに至る経路が無くなったらBFSでレベル再計算 → DFSを繰り返す…

として、計算量を減らしている。

しかし、最大流が「何でも良いから $S→T$ パスが見つかればいい」のに対し、 最小費用流はコストが最小のものを見つけないといけないので、似たような手法は使えず、1回毎に経路探索を行う必要がある。

最小費用流は「線形計画問題」にとっての代表例らしく、“最小費用流” で検索するとセットでよく出てくる。

• 線形計画問題 概要:
  • 変数 $x_1,x_2,...$ がいっぱいある
  • 制約がいっぱいある
  • 全ての制約を満たしつつ、$a_1 \cdot x_1 + a_2 \cdot x_2 + ... + a_N \cdot x_N$ を最大化せよ（$a_i$ は所与）
  • 制約は全て、変数の線形表現の等式・不等式で表せる
    • つまり、$p \cdot x_1 + q \cdot x_2 \ge r$ みたいな、「$x_i \times 係数$」を足し合わせた値に関する制約しか無い
    • $x_1 \cdot x_2$ とか $x_1^2$ とか $\log{x_1}$ とかに関する制約は無い

最小費用流では、各辺に流す流量を変数として定式化することができる。

これで定式化すると、シンプレックス法（単体法）と呼ばれる方法で、 「ほとんどの場合は高速だけど、ごく稀に指数時間かかる」ような計算量で解けるらしい。

• シンプレックス法