Educational Codeforces Round 3 E. Minimum spanning tree for each edge
ダブリング練習用の問題。HL 分解でもいける。
問題文
http://codeforces.com/contest/609/problem/E
問題概要
重み付き無向グラフが与えられるので、i 番目の辺を使った最小全域木の重みを、すべての i に対して求めよという問題。
最大の頂点数は 2・105、最大の辺の数は 2・105、最大の辺の重みは 109。
解法
i 番目の辺を使った最小全域木は以下の手順で構成できる。
- 最小全域木を構成する
- i 番目の辺を追加する
- このときできる閉路にある最大の重みの辺を削除する
それぞれ図で説明する。
1. 使う辺の制約なしで最小全域木を構成する
2. i 番目の辺を追加する
3. 閉路の中にある最大の重みの辺を削除する
したがって、この問題は u-v 間の最大の重みを求めるクエリ問題として見ることができる。 これはダブリングや HL 分解を使えばいい。
ダブリング
u-v 間クエリは u-LCA(u,v) と v-LCA(u,v) の2つのクエリに分解して計算できるので、祖先間クエリに答えられれば u-v 間クエリも答えられる。 祖先間クエリは、2i 個上との間の最大の重みを前計算しておくことで O(log n) で答えられる。
手持ちの LCA のライブラリに max の機能を付け足す形で実装した。 一度でも実装した経験があればそんなに大変な作業ではなさそう。
最大実行時間は 576 ms 。
Educational Codeforces Round 3 E. Minimum spanning ...
HL 分解
辺に情報が乗っている場合は、辺の情報を下の頂点に移せばいい。 u-v 間クエリを行う際は LCA(u, v) を含めないように注意。
分量は多いけど RMQ も HL 分解も貼るだけなので、自分で実装するのは main 関数内ぐらい。 LCA(u, v) を除外するのが面倒だけど、除外するいい方法ないかな。
最大実行時間は 624 ms。ダブリングより定数が重いかと思ったけど大して変わらなかった。
Educational Codeforces Round 3 E. Minimum spanning ...