当前位置:首页 > 图论 > 树上倍增 > 正文
GDKOI2021普及组Day2C我的世界
57+

题目大意:n个结点的树,两点之间的花费是多少?如果所有边权都是8倍,可以将中间某一段路(x->y)改为原来花费的1倍,但需要花费px+py进行中转,最小花费是多少?

解题思路

暴力跑最短路:10分,因为连太长,重复更新太多。

深搜出一条路径,暴力DP转移,估计40分。

这种题,显然用树上倍增来解决,只是中间有很多细节,考场上时间不够,就拿40吧!

首先,我们考虑a到b一条链的情况,选两个点x和y,他们之间的每条边的距离是c,a到x、y到b都是8c,从左往右和从右往左走,其实是一样的!

怎么知道选哪个结点呢?

从左往右选一个点,如果有两个点u和v选哪个?u和v距离是c,考虑从u走到v,到达v的状态相同,都是下界(边权为1倍),如果选u,费用为p[u]+c,如果选v,那么费用位p[v]+8c,谁费用小就选谁。推广到多个点也是一样的道理:[1, 4]的最优点是2,[5, 8]的最优点是7,那么只需要比较2和7谁更优,就可以得到[1, 8]谁更优了(显然134568更没用)。

从右往左选一个点,虽然方向相反了,但是在树上往上爬效果一样。因此,树上两点费用,可以直接8c走过去,也可以两边各选一个点来走下界。

这样的树上倍增还是比较好实现的,f[a][i]记录从a往上走$a^i$步的最优转成1倍边的位置。问题在于,有可能所选的最优的两个点再同一条链上!我们还需要实现从下往上走,边权变为8倍时的最有点预处理。同样是u爬上去到v,那么到达v状态都是上界(边权为8倍),如果选u,费用为p[u]+8c,如果选v,费用为p[v]+c,需要两个倍增数组。

程序中,x[i][j]记录i往上爬$2^j$步中的最优点,从该点开始边权变为c;y[i][j]记录i往上爬$2^j$步中的最优点,从该点开始边权变为8c。

对于两个结点,分别在两条链,只需要使用x数组,两边各选一个结点,往上爬变为1倍边权;如果在同一边,则需要在中转地a到最近公共祖先c再找一个结点,从他开始往上爬边权变为8倍边权,此时需要用到数组y。

注:一条链上选定一个结点边权变为1后,该结点是不需要改变的,因为换成链上其他结点,效果更差。

程序实现

GDKOI2021普及组Day2C我的世界:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter