【Jsoi2017】原力

Source

Jsoi2017
bzoj5206

Hint

请先思考后再展开

度数的数据分治

Solution

请先思考后再展开

用hash求两点间边权
设阈值T
若度数<=T,选边,考虑每条边只会被枚举T次,所以是nT
若度数>T,选点, $(n/T)^3$
取 $T=n^{1/2}$ 得到最低复杂度

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/249c.html
转载请注明出处,谢谢!