Skip to main content

__debug's Home Keep it simple, stupid

[BZOJ 2001] [HNOI 2010] 城市建设

Description

给一个 \(N\) 个点 \(M\) 条边的无向图, 有 \(Q\) 次操作.

每次操作修改一条边的边权, 并输出当前最小生成树的边权和.

每次操作并不是独立的. 可离线.

\(N \le 20000, M, Q \le 50000\)

Solution #1: 直接分治

分治很重要的一步是缩小问题规模, 这里似乎比较棘手, 因为有一些边会改变.

但是对于给定的一些询问, 我们发现可能会有一些边无论如何都要用, 还有一些边无论如何都用不上.

具体地, 如果我们将会被修改的边的边权改为 \(-\infty\) 再做 MST, 则这时加入了 MST 中的没被修改的边, 在每个询问时一定都会在 MST 中; 这时, 我们可以将这些边连接的两个点缩起来, 然后将这个边删去.

同时, 如果我们将会被修改的边的边权改为 \(+\infty\) 再做 MST, 则这时未加入 MST 中的没被修改的边, 一定不会出现在任何询问的 MST 中. 这些边也可以删去.

经过计算, 可以发现点数和边数都降至了 \(O(Q)\) 的级别 (点数 \(Q + 1\), 边数 \(2Q\)), 就可以分治下去了.

但是这种方法并不是很好实现, 至少我的方法很难写.

记得递归右一半的时候不要忘记应用左边的询问, QAQ.

Solution #2: LCT + 线段树维护分治结构

留坑待填, 不过写过类似的题目, 并且比较好写.

好像要卡常…

Comments

Comments powered by Disqus