考察
警備員iが頂点vを守れる条件dist(p_i,v)≤h_iは、p_iから体力h_iで出発し、辺を一つ進むたび体力を1減らして、非負のままvへ着ける条件と言い換えられる。
頂点vで必要なのは、どの警備員が来たかではなく到達時の残り体力の最大値d_vだけである。残り体力xでvへ来れば、隣接頂点へx−1を伝播できる。
棄却する候補: 各警備員を始点に深さh_iまでBFSし、訪れた頂点を警備済みにする。
警備範囲が大きく重なると同じ頂点・辺を警備員ごとに繰り返し走査し、Kとグラフサイズの積に達し得る。
採用する候補: 各頂点へ届く最大残り体力を状態にし、その値が最大の頂点から優先度付きキューで確定・伝播する。
警備員の個別BFSを合成する必要はない。
dを−1で初期化し、各(p_i,h_i)でd[p_i]をh_iにして最大heapへ入れる。最大の(x,v)を取り出し、古い候補なら捨てる。x>0なら各隣接uへx−1を緩和し、最後にd[v]≥0の頂点を昇順で列挙する。
典型の発動条件
多始点の最大値伝播
発動条件: 複数の源が異なる初期資源を持ち、辺を進むたび一定量減る資源の最大到達値を求めたいとき。
全警備員を初期labelとして同じ最大heapへ入れ、頂点ごとの最大残り体力だけを伝える。
Dijkstra型のlabel-setting
発動条件: 優先度最大の暫定値を確定でき、後続遷移がその順序を逆転させないとき。
残り体力が最大の頂点から確定し、1減らした値で隣接頂点を緩和する。
問題固有の要素
距離制約h_iを『到達時に残る体力h_i−dist』へ変えると、警備員ごとの球の和集合が一つのmax-plus伝播になる。
別の問題へ持ち帰る視点: 始点ごとに半径が異なる到達可能性では、半径から移動距離を引いた残余量を頂点labelとして統合する。
正当性
未確定候補で最大の体力xを持つ頂点vを取り出すと、別経路が後からvへ届ける体力はxを超えない。これは辺ごとに値が1だけ減る、Dijkstra法の符号を反転したlabel-settingである。 複数の警備員は、各p_iの初期値をh_iにする多始点として同じ探索へ同時投入できる。警備員の個別BFSを合成する必要はない。 より小さい体力で同じ頂点へ着く経路は以後も大きい体力の経路を上回れず、最大値一つへ支配関係でまとめられる。
実装上の注意
- 同じ頂点の古いheap entryが残るため、取り出したxが現在のd[v]と一致しなければ処理しない。x=0からは負値を伝播させない。
- 警備員の頂点は相異なるが、一般化して同じ始点があっても初期値の最大を取る形にしておくと更新規則が一貫する。
復習の核
- 警備員二人の範囲が重なる小グラフでh_i−distを直接書き、頂点ごとの大きい値だけ残しても、その先の警備可能性を失わないことを確認する。
計算量と制約
時間
O((N+M+K)log(N+M+K))、N頂点M辺K警備員。
空間
O(N+M+K)、隣接表とheap。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right); 1 \leq K \leq N; 1 \leq a_i, b_i \leq N; The given graph is simple.; 1 \leq p_i \leq N; All p_i are distinct.; 1 \leq h_i \leq N; All input values are integers.
出典