https://kanpurin.hatenablog.com/entry/2021/11/27/033005

メモがてら書きます．

問題概要

長さ ${N}$ の数列 ${(x_1,x_2,\dots ,x_N)}$ を作る．各 ${x_i}$ には ${A_{i,1},A_{i,2},\dots, A_{i,M}}$ ${M}$ 個の選択肢があり， ${A_{i,j}}$ を選ぶと ${C_{i,j}}$ のコストがかかる．さらに，各 ${1\leq i < j\leq N}$ について ${|x_i-x_j|×W_{i,j}}$ のコストが追加でかかる．コストの総和の最小値を求めよ．

${2\leq N\leq 50\\ 2\leq M\leq 5\\ 1\leq A_{i,j} < A_{i,j+1}\leq 10^6\\ 1\leq C_{i,k}\leq 10^{15}\\ 1\leq W_{i,j}\leq 10^6}$

解説

複数の選択間にコストがある+制約的にProject Selection Problemっぽい．Project Selection Problemは最小カット(最大流)で解ける．
以下のグラフで頂点をS or Tに分割するカットを考える．

これは ${M=4}$ の場合において以下のように辺にコストを割り当てると，以下の各カットが各選択に対応する．

しかし，以下のようなカットも可能になってしまうので

以下のようにコスト ${\infty}$ の辺を張れば，最小カットは上の ${M}$ 通りのうちどれかになる．

これでコスト ${C_{i,j}}$ のグラフ表現はできたのでコスト ${|x_i-x_j|×W_{i,j}}$ のグラフ表現を考える．
${x_i,x_j}$ 間のコストが以下の表のようになっているとする( ${W_{i,j}=1}$ )．実は，この表がMonge性を満たしていればグラフ表現可能．今回の関数 ${|x_i-x_j|×W_{i,j}}$ がMonge性を満たすことはすぐに分かる．

基本操作

${k}$ 行目の各要素から ${c}$ を引く．この操作は ${x_i=A_{i,k}}$ を選んだときのコスト ${C_{i,k}}$ に ${c}$ を加えることに対応する．
${k}$ 列目の各要素から ${c}$ を引く．この操作は ${x_j=A_{j,k}}$ を選んだときのコスト ${C_{j,k}}$ に ${c}$ を加えることに対応する．
${(p,q)}$ 成分 ${(1\leq p\leq a,b\leq q\leq M)}$ に ${c(\geq 0)}$ を加える．この操作は ${x_j}$ の選択を表す ${b-1}$ 番目の頂点から ${x_i}$ の選択を表す ${a}$ 番目の頂点にコスト ${c}$ の辺を張ることに対応する．

これらの操作はMonge性を満たす行列に適用してもMonge性は保存される．

具体的にグラフを構築していく．

${1\leq k\leq M}$ 行目に対して各要素から ${(k,1)}$ 成分の値を引く．

${1\leq k\leq M}$ 列目に対して各要素から ${(M,k)}$ 成分の値を引く．

3つ目の"基本操作"は累積和のようになっているので累積和の逆をして各成分に加える値を計算する．3つ目の"基本操作"に ${c=(a,b)+(a+1,b-1)-(a+1,b)-(a+1,b-1)}$ として適用

これはMonge性から必ず非負になる．もうちょっと考えると正の成分は ${O(M)}$ 個になることが分かる．

${C_{i,k}}$ が負になることがあるが， ${\underset{1\leq k\leq M}{\min}C_{i,k}}$ を ${C_{i,k}(1\leq k\leq M)}$ から引けばいい．ただし最終的な答えに ${\underset{1\leq k\leq M}{\min}C_{i,k}}$ を足す必要がある．