最小費用流で解ける問題

最初の $a_1$ 個は $b_{k,1}$ 円
次の $a_2$ 個は $b_{k,2}$ 円
次の $a_3$ 個は $b_{k, 3}$ 円
次の …

で売れる。ただし、b は狭義減少列で、負の値があっても良い。得られるお金の最大値を求めよ（ARC137E）

解答略

双対問題

最小費用流問題は線形計画問題として定式化すると、\begin{equation*}
\begin{array}{ll@{}ll}
\text{minimize} & cx &\\
\text{subject to}&\overline b \geq Ax \geq \underline b\\
& \overline u \geq x \geq \underline u
\end{array}
\end{equation*}となる。この値を下から評価してみる。

卸業者 A : 辺 $e$ を関税 $c_e$ で通れる。各頂点の需給を満たすように輸送したい。転売屋 B : 頂点 $i$ で物価 $\pi_i$ で売買して需給を満たしたい。B は関税が掛からない。B は在庫と資金が無限にあるので買った量と売った量は一致しなくてもよい。 B は A の輸送費（主問題）より安い価格を提示して、シェアを奪いたい。

$\partial x_v = b_v$ のとき、頂点 $v$ での売買に掛かる費用は $\pi_vb_v$ である。B は $\min(\pi_v \overline b_v , \pi_v \underline b_v)$ を費用に加える。

B が頂点 $u$ で買い頂点 $v$ で売るための費用は $\pi_u-\pi_v$ である。従って、A は辺 $e=(u, v)$ の単位流量当たり、少なくとも $c_e^\pi = c_e-(\pi_u-\pi_v)$ だけ B より費用が大きい。従って、B は $\min(c_e^\pi \overline u_e, c_e^\pi \underline u_e)$ を費用に加える。$c_e^\pi$ を簡約費用と呼ぶ。

B はできるだけ高い額を提示したいので、
$$\mathrm{maximize} \quad \sum \min \left(\pi_v \overline b_v , \pi_v \underline b_v\right)+\sum\min\left(c_e^\pi \overline u_e, c_e^\pi \underline u_e\right)$$である。この値が主問題の下からの評価になっていること（弱双対性）は作り方から明らかである。更に、主問題と値が等しいことがいえるが、それは非自明で強双対性定理が必要である。また、相補性条件から最適解では

$x_e = \underline u_e$ ならば $0 \leq c_e^\pi$
$\underline u_e < x_e < \overline u_e$ ならば $c_e^\pi=0$
$x_e = \overline u_e$ ならば $c_e^\pi \leq 0$
$\partial x_v = \underline b_v $ ならば $0 \leq \pi_v$
$\underline b_v < \partial x_v < \overline b_v $ ならば $\pi_v = 0$
$\partial x_v = \overline b_v $ ならば $\pi_v \leq 0$

が成り立つ。

先の目的関数を線形計画問題として定式化するには、min を消去する必要がある。そこで $\pi = \pi^++\pi^-, c^\pi=c^{\pi+}+c^{\pi-}$ という変数変換をして、\begin{equation*}
\begin{array}{ll@{}ll}
\text{maxmize} & \overline b \pi^-+\underline b \pi^+ +\overline u c^{\pi-} +\underline uc^{\pi+} &\\
\text{subject to}& c^{\pi+} + c^{\pi-} = c-A^T (\pi^-+\pi^+)\\
& c^{\pi-} \leq 0 \\
& c^{\pi+}\geq 0 \\
& \pi^- \leq 0 \\
& \pi^+ \geq 0 \\
\end{array}
\end{equation*} となる。この変換で最適解は変化しない。

頂点 $v$ に出る辺しか存在せず $\underline b_v = 0$ である場合

$\pi_v \geq 0$ において $\sum \min \left(\pi_v \overline b_v , \pi_v \underline b_v\right)$ は定数 $0$、 $\sum\min\left(c_e^\pi \overline u_e, c_e^\pi \underline u_e\right)$ は単調減少だから、最適解では $\pi_v \leq 0$ である。これは、$\pi_v \geq 0$ ならば転売屋 B は損を避けて、頂点 $v$ で買い物をしない選択肢 $\partial x_v = 0$ を取ることができ、このとき、A との価格差が最も開くのが $\pi_v = 0$ であることからきている。

頂点 $v$ に入る辺しか存在せず、$\overline b_v = 0$ である場合

同様にして $\pi_v \geq 0$ となる。

$\overline b_v = \infty$ である場合

$\pi_v \geq 0$ である。$\pi_v < 0$ だと B は $v$ で買うことで無限にコストを下げられてしまう。

$\overline u_e = \infty$ である場合

$c_e^\pi \geq 0$ である。

二部グラフの重み付きマッチング

以上の特別な場合として二部グラフの重み付きマッチングの符号を反転した問題があり、
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maxmize} & \sum_{v \in A} \pi_v^- -\sum_{v \in B} \pi^+ &\\
\text{subject to}& c^{\pi+} = c-A^T (\pi^-+\pi^+)\\
& \pi_v^- \leq 0 \\
& \pi^+ \geq 0 \\
& c^{\pi+} \geq 0 \\
\end{array}
\end{equation*}のように書ける。ただし、部集合 $(A, B)$ 、辺 $e$ の重み $-c_e$ としている。逆全域木問題やABC224Hがこれに帰着される。二部グラフの最小頂点被覆と捉える方法もある。

例題

$N$ 個の区間 $[s_i,t_i]$ は次の条件を満たさなければならない。

区間のペアの集合 A が与えられる。任意の $(i, j) \in A$ について、$i$ 番目の区間と $j$ 番目の区間が共通部分を持ってはならない。
区間のペアの集合 B が与えられる。任意の $(i, j) \in B$ について、$i$ 番目の区間と $j$ 番目の区間は共通部分を持たなければならない。
$s$ は単調増加
区間 $i$ は長さ $p_i$ までは単位長さ当たり $a_i$、$p_i$ の超過分は単位長さ当り $b_i$ の得点が貰える。ただし $a_i \geq b_i$ である。得点の総和が $W$ 以上でなければならない。

以上の条件の下で、$\max(t_i)-\min(s_i)$ を最小化せよ。（HUPC2020H）

$\min(s_i) = 0$ と仮定して一般性を失わない。$\max(t_i)-\min(s_i)$ が大きいほど、得点が W 以上という条件を満たしやすいので、二分探索。$\max(t_i),\min(s_i)$ を固定すると、得点の最大化は最小費用流の双対になる。

二部グラフ $G =(A \cup B, E)$ がある。各頂点に非負整数を書き込みたい。$v_i \in A$ に書き込む数を $a_i$、$u_j \in B$ に書き込む数を $b_j$ と置く。各辺 $e=\{v_i,u_j\}$ について $a_i + b_j \geq c_{e}$ を満たさなければならない。この下で $\sum a_i + \sum b_j$ を最小化せよ。（ABC224H）

行列 $a$ と数列 $b, c$ が与えられる。$\sum_{i < j} a_{i,}|x_i-x_j| +\sum b_i|x_i-a_i|$ を最小化する数列$x$ を求めよ。（ICPC2020NERC O）

$y_i=x_i-a_i$ と変数変換すると、$\sum b_i|x_i-a_i|$ も計算できる。