NOI 2020 Finals - Aesthetic
概要
問題へのリンク
Author : Cyanmond
とても難しい。
解法
まず、辺$ iの重みを変える場合その重みは$ \displaystyle W_i + \max_{k=i+1}^{M} W_kとしてよいことが簡単にわかる。これで小課題 2 を解くことができる。
証明 : ある辺の重みを大きくしていったとき最短パスが短くなることはありえない。
簡単な考察として、$ 1-N最短パスに必ず含まれる辺以外は辺の重みを変えても$ 1-N最短経路の長さは変わらない。そのため、まず$ 1-N最短パスに必ず含まれる辺の集合を高速に求めることを考える。
いずれかの$ 1-N最短パスに含まれる辺の集合からなる部分グラフ$ Hを考える。全ての$ 1-N最短パスに含まれる辺集合は、$ Hの橋と一致する。そのため、まず$ Hを求め (これは簡単) その後 lowlink なりで橋を列挙すればよい。
以下、(初期状態のグラフの)$ 1-N最短パス長を$ dとおく。
$ 1-N最短パスに必ず含まれる辺を$ X_1, X_2, \cdots ,X_Pとする。各$ i \ (1 \leq i \leq P)について、辺$ X_iの重みを変えたときの$ 1-N最短パス長を考える。
まず、辺$ X_iを通るような最短パス長は$ d + \max_{k=X_i+1}^{M} W_kである。これを$ xとおく。
また、辺$ X_iを通らないような最短パス長を$ yとおく。
このとき、辺$ X_iの重みを変えたときの$ 1-N最短パス長は$ \min(x, y)である。
$ xを各$ iについて求めることは簡単なので、問題は$ yとなる。つまり、各$ i \ (1 \leq i \leq P)について$ X_iを通らないときの$ 1-N最短パス長を高速に求めたい。これは実はできて...
まず、$ Xを$ 1-N最短パスに出てくる順番にソートする。
これは一意に定まるが、長さ$ 0の辺の扱いに気を付ける必要がある。
頂点$ 1を始点としたダイクストラ法を行うときに、ついでに以下のように定義される数列$ Qを求めておく。
$ Q_v := 1- v最短パスに出てくる$ X上の頂点の個数
もしくは出てくる$ X上の頂点のうち index の最大値と考えてもよい。同じことにはなるが、こちらの方が捉え方として自然か。
その後、各$ i \ (1 \leq i \leq M)について以下のことをする。
辺$ iが$ Xに含まれている場合無視する。
$ Q_{A_i} = x, Q_{B_i} = yとおく。$ x > yの場合$ A_i, B_iを swap して考える。
$ j = x + 1, x + 2, \cdots ,yについて、辺$ X_jを通らないような最短パス長を$ \mathrm{dist}(1, A_i) + W_i + \mathrm{dist}(B_i, N)で chmin する。
これは双対セグメント木ないしイベントソートで高速化ができる。
結局以上の全体での計算量は$ O(N + M \log M)となる。