[BZOJ2286/Luogu2495][SDOI2011]消耗战(虚树,树型动态规划)

发布于 2018-05-25  133 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2286/Luogu2495][SDOI2011]消耗战(虚树,树型动态规划)

Description

在一场战争中,战场由n个岛屿和n-1个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为1的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他k个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。
侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到1号岛屿上)。不过侦查部门还发现了这台机器只能够使用m次,所以我们只需要把每次任务完成即可。

Tag

虚树,树型动态规划

解决思路

把虚树建立出来后,在树上动态规划求解最小切割的代价。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2286/Luogu2495][SDOI2011]消耗战(虚树,树型动态规划)


HNCJ OIer