読者です 読者をやめる 読者になる 読者になる

重み付き区間スケジューリング

まずは蟻本から

Intervals (POJ No.3680)

N個の重み付き閉区間がある。i番目の区間(a_i, b_i)をカバーし、重みw_iを持つ。この中からk個より多くの区間で覆われている点が存在しないように幾つかの区間を選び、重みの和を最大化せよ。

K = 1の場合、N個の区間から互いに交差しないように選んだときの重みの和の最大値を求める問題(=区間グラフの最大重み安定集合問題, 重み付き区間スケジューリング)

区間グラフの最大安定集合問題
  • DPの日本語の式 (1)
  • DPの数式 (2)
  • DPのグラフ的解釈 (3a, 3b)
    • このようなグラフの (4) 問題を解いていると考えることができる。

どの点もK個より多くの区間で覆われない = (4)

このようなグラフにおけるv_0からv_{m-1}への1つの最短路のコストは、K=1の場合のDPで得られた値の符号を反転したものになる。

このグラフで、-w_iの重みをつけた辺をパスに含むことが区間iを選ぶことに対応する。したがって、この辺の容量を1とし、他の辺の容量を∞としたネットワークを考えれば、その流量Kv_0 - v_{m-1}フローはK個の集合の重みの和に対応する。よって、最小費用流のアルゴリズムで解くことができる。グラフに負の辺が含まれることより、負の辺に予め目一杯流しておく方式を取る。


解答
1. dp[i] := b_k \le x_iであるような区間のみを考えた場合の最大の重み
2. dp[i] = max(dp[i-1],\ max\{dp[j]\ +\ w_k\ |\ a_k\ =\ x_j\ かつ\ b_k\ =\ x_i\})
3a. m個の端点x_iに対応する頂点v_iを作る。
3b. v_{i-1}からv_iへコスト0の辺をはり、各区間kについてa_k\ =\ x_jかつb_k\ =\
 x_iであるようなijに対してv_jからv_iへコスト-w_kの辺を張る。
4. 最短路問題
5. 互いに交差しないような区間の集合K個に分割できる