久しぶりですごい時間がかかったのでメモ
大体次の問題。
- $N$ 頂点 $M$ 辺の有向グラフと非負整数 $K$ が与えられる。各辺には非負整数の重みが付いていて、辺 $e$ の重みを $d_e$ とする。$K$ は $1 \to N$ の最短距離より小さくない。 $1$ 円払うと好きな辺の重みを $1$ 増やせる時、頂点 $1$ から $N$ の最短距離を $K$ にするために必要な最小コストは？ 構築あり: 各辺について何回伸ばすかも復元する必要あり
まず、この問題はほぼ最小費用循環流の双対問題そのものなので、構築がなければ難しくない。というか大体コレ J - Longest Shortest Path
最小費用循環流:
$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $e$ には非負の容量 $c_e$ と(非負とは限らない)コスト $d_e$ が付いている。辺ごとに $0 \le f_e \le c_e$を満たす流量 $f_e$ を割り当てる。頂点ごとに流量の出入りが等しい必要がある。 $\sum_e f_e d_e$を最小化せよ。
最小費用循環流の双対問題:
$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $e$ には非負整数 $c_e$ と整数 $d_e$ が付いている。頂点ごとにポテンシャル $p_v$ を割り当て、$- \sum_{e = (u \to v)} c_e \max(0, p_v - p_u - d_e)$ を最大化せよ。
この2つの問題はLP双対から得られる問題である。そのため、同じグラフに対するこの2つの問題の答えは必ず一致する。なお、(答えが $-1$ 倍されるが)後者の目的関数は「$\sum_{e = (u \to v)} c_e \max(0, p_v - p_u - d_e)$ を最小化」としたほうが見通しがいいと思う。参考: 双対性 | PPT 。
今回の問題
は、牛ゲー(最短経路問題の双対)に思いを馳せると、$(u, v, c, d) = (N, 1, \inf, -K), (1, N, \inf, K)$ の $2$ 辺を追加して、最小費用循環流の双対問題を解けばよいことがわかる。追加した $2$ 辺は $p_N - p_1 = K$という制約を追加することに対応する。これは普通の逐次最短路法+少しの工夫でもいいし、強力なアルゴリズムを用いてもいい (参考: https://judge.yosupo.jp/problem/min_cost_b_flow 周りの諸々)。つまり、この問題の本質は「最小費用循環流の双対問題の解 $p_v$ をどうやって復元するのか？」という点になる。
$p_v$ の復元方法
結論から言うと、大体のライブラリは内部にこの $p$ を変数として持っているし、最小費用循環流を流せるだけ流した後にベルマンフォード法を行えば直接求まる。どういうことだろうか？
まず、最小費用循環流の基礎として、次が成立する。
- 最小費用循環流において、ある流量 $f$ が最適解である $\Leftrightarrow$ 残余グラフに負閉路が存在しない
($\Rightarrow$)は自明、($\Leftarrow$)は自明ではないけど、現在の流量 $f$ と最適解の流量 $f'$ の差分に注目すると示せる。
また、負閉路が存在しない、またその時のみ、残余グラフの(容量が $0$ でない)各辺について $p_v - p_u - d_e \le 0$ を満たすポテンシャル $p$ が存在する。これはベルマンフォード法などで計算可能。また、このポテンシャルは多くのライブラリが内部に直接変数として持っている。
逆に言うと、流量条件を満たす流量 $f$ と、$f$ の残余グラフにおいて $p_v - p_u - d_e \le 0$を満たすポテンシャル $p$ が見つけられたなら、そのペア $(f, p)$ は $f$ が最適解であるという証拠になる。…というわけで https://judge.yosupo.jp/problem/min_cost_b_flow では、流量 $f$ に加えてこのポテンシャル $p$ も復元させている。
2つのポテンシャル
この記事では $2$ つのポテンシャル $p$ が登場している。ひとつは「最小費用循環流の双対問題」で紹介した $p$ であり、これが今回の問題を解くために必要なものである。もう一つは最小費用循環流の最適解の残余グラフにベルマンフォード法を行うと計算可能な $p$ である。後者が計算可能なのはわかったが、どうやって前者を計算すればいいのか？実は後者の $p$ をそのまま前者の $p$ にすればいい(ええー！)
今までの話を再度まとめる。
計算可能なことがわかっているもの : 次の条件を満たすペア $(f, p)$
- 各辺 $e$ について、$0 \le f_e \le c_e$
- 各頂点について、流量の出入りの総和が等しい
- $f_e > 0$ を満たす辺 $e = (u \to v)$ について、$p_u - p_v + d_e \le 0$
- $f_e < c_e$ を満たす辺 $e = (u \to v)$ について、$p_v - p_u - d_e \le 0$
ここで、「最小費用循環流」の答えは $\sum_e f_e d_e$ となる。
計算したいもの: $\sum_{e = (u \to v)} c_e \max(0, q_v - q_u - d_e)$ が「最小費用循環流の答えの $-1$ 倍」となる $q$。
証明したいこと: $p$が求める $q$ のうちひとつであること。つまり、$\sum_{e = (u \to v)} c_e \max(0, p_v - p_u - d_e)$ = $- \sum_e f_e d_e$ を示せればよい。
証明
$f_e < c_e$ならば、$p_v - p_u - d_e \le 0$、つまり $\max(0, p_v - p_u - d_e) = 0$であるので、$\sum_{e = (u \to v)} c_e \max(0, p_v - p_u - d_e)$
$= \sum_{e = (u \to v)} f_e \max(0, p_v - p_u - d_e)$ となる。
また、$f_e > 0$ならば $p_v - p_u - d_e \ge 0$ なので、
$= \sum_{e = (u \to v)} f_e (p_v - p_u - d_e)$ となる。
そして、$f$ を単純閉路に分解して考えることで
$= \sum_{e = (u \to v)} - f_e d_e$
が言えるため、示せた。
結論
https://judge.yosupo.jp/problem/min_cost_b_flow を解くライブラリを準備(or 何らかの方法で入手)しておけば、張ると通る
