2014JOI春合宿2-1 Water Bottle 解説

問題リンク

解説

まず、$P$ 頂点のグラフを構築できれば、その中での経路のうち辺のコストの最大値の最小化をすればいいことになる。 このグラフ上でクラスカル法みたいなことをやれば、木上の問題になるのもすぐわかる。

さて、この木の構築方法だが、各建物から BFS をしながら Union-Find でつなげていくという方法がすぐ思いつくだろう。 しかし、この方法では、長さ $i$ の辺より $2i+1$ の辺が先に検出されてしまうことがある。

最初に BFS をして、$O(HW)$ 個のマスの境界を見て長さを求め、これらをソートしてクラスカル法を行えば、$O(HW\log HW)$ で木を構築できる。

経路のうちでの辺のコストの最大値の最小化は、並列二分探索+UnionFind、SparseTable+HLD、ダブリングなど、いくらでも方法があるので、この問題が解けた。