問題
yukicoder 競プロ典型 90 問 期末試験 J – Many Shortest Path Problems
問題リンク：https://yukicoder.me/problems/no/1600
解説
利用する典型テクニック
- Union-Find
- 最小全域木・クラスカル法の原理
- Lowest Common Ancestor
「辺 $z_i$ を通らない」を無視した場合
辺の番号を重みとした最小全域木(全域木 $T$ )に含まれる辺のみ考える。
辺 $i$ を使った任意のパスの長さは、番号が $i$ より小さい辺のみを使ったパスの長さより大きいです。番号が $i$ より小さい辺のみを通って行き来できる $2$ 頂点を辺 $i$ が繋いでいても、最短パスは辺 $i$ を通りません。したがって、辺の番号を重みとしたクラスカル法で作る、最小全域木に含まれる辺のみを考えればよいとわかります。
※重みが相異なれば最小全域木は一意であり、したがってプリム法などを用いて求めてもよいです。
全域木 $T$ 上の最短パス長をクエリ $O( \log N )$ 時間で求める。
頻出のテクニックなので、ここでは説明を省略します。おそらく、ここで Lowest Common Ancestor を求めると思いますが、これは後にも用います。
その最短パスは辺 $z_i$ を含むか
全域木 $T$ 上の $x_i,y_i$ 間の最短パスが辺 $z_i$ を含まなければ、それが答えです。
$2$ 点間距離の性質を用いて、パスが辺 $z_i$ を含むか判定する。
今、辺の長さがすべて $1$ であるとします。( $\mathrm{mod}$ をとるとできません )
木上で、 $2$ 頂点 $u,v$ 間の最短パスの長さを $\mathrm{dist}(u,v)$ で表します。
$(u,v)$ 間の最短パスが辺 $(a,b)$ を含む場合に限り、下のいずれかが成り立ちます。
- $\mathrm{dist}(u,a)+\mathrm{dist}(b,v)\lt\mathrm{dist}(u,v)$
- $\mathrm{dist}(u,b)+\mathrm{dist}(a,v)\lt\mathrm{dist}(u,v)$
よって、 $O( \log N )$ 時間でこれを判定できます。
別の方法：根が動的な LCA
ところで、頂点 $r$ を根としたときの $x,y$ の Lowest Common Ancestor を $\mathrm{LCA}_r(x,y)$ と表すと、
- $\mathrm{LCA}_r(x,y)=\mathrm{LCA}_0(x,y) \oplus \mathrm{LCA}_0(x,r)\oplus \mathrm{LCA}_0(y,r)$ ( $a\oplus b$ は $a$ と $b$ のビットごとの排他的論理和)
が成り立ちます。(noshi91 様の言及：https://twitter.com/noshi91/status/1336562191080726528)
これを用いても その最短パスは辺 $z_i$ を含むか を判定できます。
辺 $z_i$ を通れないときに追加で考慮する辺
全域木 $T$ 上の $x_i,y_i$ 間の最短パスは辺 $z_i$ を通るとします。
任意の辺 $e$ について、辺 $e$ を通れなくなったときに追加で考慮する辺は一意。
木から辺 $e$ を削除すると、 $2$ つの連結成分になります。クラスカル法により、元のグラフでこの $2$ つの連結成分をつなぐコスト最小の辺を追加すると、この時点での最小全域木になります。
この「コスト最小」に注目します。全域木 $T$ に含まれない辺のうち、コストの昇順に見ます。辺 $d=(s,t)$ を見るとき、
- $s,t$ 間の最短パス上の辺であって、
- その辺を削除したとき追加する辺がまだ決まっていないものについて、
その辺を削除したとき追加する辺は $d$ に決まります。
辺 $e$ を削除したときに追加する辺を $\mathrm{C_{over}}[e]$ と表します。
全ての辺 $e$ について $\mathrm{C_{over}}[e]$ を、 $O((N+M)\log N)$ 時間で求める。
$1$ 度見たパス上の辺をうまく飛ばすテクニックを使います。
全域木 $T$ を根付き木とみなし、以下を準備します。
- 根と異なる頂点 $x$ の親を $\mathrm{P}[x]$ と表します。
- 頂点 $p$ と頂点 $\mathrm{P}[x]$ を結ぶ全域木 $T$ の辺を $\mathrm{P_{edge}}[p]$ と表します。
- Lowest Common Ancestor(以下、 LCA と呼ぶ)を $O(\log N)$ 時間で求められるようにします。
- Union-Find を用意します。以下、この Union-Find の状態を関数 $f$ で表し、 $f(i)=f(x)$ となる $i$ すべてについて $f(i)\leftarrow f(y)$ と上書きする操作を、 $f(x)\leftarrow f(y)$ で表します。
全域木 $T$ に含まれない辺のうち、コストの昇順に見ます。辺 $e=(s,t)$ を見るとき、以下の手順を行います。
- $g$ を $s,t$ の LCA とする。 $p\leftarrow f(s),f(t)$ について以下を行う。
- $p\neq g$ の間、以下を繰り返す。
- $\mathrm{C_{over}}[\mathrm{P_{edge}}[p]]\leftarrow e$
- $f(\mathrm{P}[p])\leftarrow f(p)$
- $p\leftarrow f(p)$
- $p\neq g$ の間、以下を繰り返す。
$\mathrm{C_{over}}[e]$ は代入されないことがありますが、そのときの値を $-1$ とします。
これと似たテクニックは過去の PAST に登場しています。
辺を追加したときの最短経路
$\mathrm{C_{over}}[z_i]$ の両端と $x_i,y_i$ で最短パス長を求めてクエリに答える。
(2021年7月22日に更新しました)
全域木 $T$ 上の $x_i,y_i$ 間の最短パスは辺 $z_i$ を通るとします。 $\mathrm{C_{over}}[z_i]$ は $2$ 頂点 $a,b$ を結ぶとします。
クエリの答えは
- $x_i,a,b,y_i$ を順に通るパス
- $y_i,b,a,x_i$ を順に通るパス
のどちらかですが、仮にどちらかわかっている(前者であるとする)とすると、答えは
- 全域木 $T$ 上で $x_i,a$ 間の最短パス長 (辺 $z_i$ で分割される連結成分の内部なので、辺 $z_i$ を含まない)
- 辺 $\mathrm{C_{over}}[z_i]$ の長さ
- 全域木 $T$ 上で $b,x_i$ 間の最短パス長
を足し合わせたものです。ところで、すべての辺の長さを $1$ としてこれを計算すると、上の $2$ 通りのパスのうち正しいほうの長さが小さくなり、これを判定できます。
従って、クエリごとの計算量は $O( \log N)$ です。
まとめ
以上を用いて、全体のアルゴリズムは次のようになります。
- 最小全域木 ( 全域木 $T$ ) を求める
- 辺 $z_i$ を通れないときに追加で考慮する辺 $\mathrm{C_{over}}[z_i]$ を求める
- 各クエリに以下で答える
- その最短パスは辺 $z_i$ を含むか を判定(1)
- (1) が No なら、 「辺 $z_i$ を通らない」を無視した場合
- (1) が Yes で、 $\mathrm{C_{over}}[z_i] \neq -1$ なら 辺を追加したときの最短経路
- (1) が Yes で、 $\mathrm{C_{over}}[z_i] = -1$ なら答えは $-1$
これで、この問題が $O((N+M+Q) \log N)$ 時間で解けました。
やることが多いので、実装ミスを起こしやすいです。対策として、この記事のようにうまく分割し、わかりやすい名前の関数にすることで、デバッグの効率化やミスの減少を期待できます。
提出コード
コンテスト中の AC ： https://yukicoder.me/submissions/676404
アルゴリズムはおおよそ同じですが、細部ではこの解説と異なるかもしれません。