「Jsoi2017」原力

Source

Jsoi2017
bzoj5206

Hint

请先思考后再展开

用hash求两点间边权
度数的数据分治

Solution

请先思考后再展开

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

T取 $2\sqrt m$ 会比较恰当

upd:其实用这里的方法会很好写

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