BZOJ-2001. [HNOI2010]City城市建设

题目给定一个有 n 个节点,m 条边的有向图,以及 q 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,n\leq 20000, m \leq 50000, q \leq 50000

看了这篇题解才会做的QAQ

题目核心思想是分治以及缩小图的规模,有两个操作

Contraction:删除必须边

把待修改的边标记成 -\infty,然后跑一次最小生成树,显然这时候出现在生成树中非 -\infty 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边

Reduction:删除无用边

把待修改的边标记成 \infty,然后跑一次最小生成树,没出现在生成树中的非 \infty 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,\infty 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治

然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/04/bzoj-2001

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.