[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)

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


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

本文链接地址:[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)

Description

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划,我们想知道:
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少

Tag

虚树,树型动态规划

解决思路

建立出虚树后,现在要求的就是各个关键点之间的路径长度之和,两端均为关键点的最长和最短路径,在虚树上动态规划求解。

代码

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

本文链接地址:[BZOJ3611/Luogu4103][HEOI2014]大工程(虚树,树型动态规划)


HNCJ OIer