牛ゲー(最短経路問題の双対問題が線形計画問題)

牛ゲー

最短経路問題の双対問題を考えると線形計画問題になるということ

最短経路が定まっており、始点 s からの頂点 v, u への最短距離を d_v, d_u とする。またコスト w の v から u への辺を e(v,u) とすると

d_u - d_v \le w(const) \tag{1}

と表すことができる。逆にこのような制約式で定式化される問題は最短経路問題に帰着して解くことができる。

例題

H: Asteroids2 - 東京大学プログラミングコンテスト2013 | AtCoder

考え方

小惑星を破壊できるときの条件を定式化しよう。縦方向へのレーザーを x_i 横方向へのレーザーを y_i としておく。そのとき

a_k \le x_i+y_i \le b_k \tag{2} 0 \le x_i \le p_i \tag{3} 0 \le y_i \le q_i \tag{4}

となる。

(1) の形にするためにy_i は -y_i と変形する。また変数 Z(=0) を導入する。(3),(4) は以下のようになる。

0 \le x_i - Z \le p_i \tag{5} 0 \le Z - y_i \le q_i \tag{6}

以下のように不等式を分けて考えることができて、(1) の形にすることができた。よって最短経路問題に帰着することができた。

  • Z - x_i \le 0
  • y_i - Z \le 0
  • x_i - Z \le p_i
  • Z - y_i\le q_i
  • y_j - x_i \le -a_k
  • x_i - y_i \le b_k

x 軸 y 軸それぞれ 2N 個の点と Z の点上での最短経路を求めればよい。負閉路が存在する場合は最短経路が定まらないので条件を満たす値は存在しない。最短経路が定まれば条件を満たす値が存在する。よって閉路の有無を検出すればよい。これはベルマンフォード法で検出することができる。

初期値の値 cost[Z] に対して cost[Z] \lt 0 となる場合は負閉路が存在する、そうでない場合は存在しないと判定すれば良い。

Submission #4081808 - 東京大学プログラミングコンテスト2013

類題

N - 何かグラフの問題

参考