描述
给出有n个点, m条边的无向图, 每次修改一条边的权值, 求修改后的最小生成树的大小. 修改次数 ≤ 50000.
分析
- 还是CDQ分治, 但是有点特殊. 目前的CDQ分治还是停留在看题解看别人代码才理解的层面.
- 有一些边一定在部分修改后的最小生成树中, 这是优化的中心思想吧.
- 然后一个减少边的操作, 一个减少点的操作. 看课件吧.
- 减少点的方法是缩点, 用并查集.
- 一开始想用全局变量d, n, m, ans代替函数参数传递. 后来发现因为分治的缘故这样做是不行的.
代码
BZOJ-2001-city城市建设-HNOI2010-CDQ分治
原文：http://blog.csdn.net/qq_21110267/article/details/44698825
