BZOJ 5180 [Baltic2016]Cities


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5180

题意:给定 n 个点,m 条双向边的图。其中有 k 个点是重要的。每条边都有一定的长度。现在要你选定一些边来构成一个图,要使得 k 个重要的点相互连通,求边的长度和的最小值。


斯坦纳树裸题... 第一次写... 就是个状压 dp 嘛...

\(f_{S,i}\) 表示以 i 为根的子树,联通状态为 S 的最小费用,不同层转移是一个枚举子集的过程,同层的转移用每条边去转移,发现具有后效性,所以用最短路跑。

交了两发卡了 100s 的 OJ...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 5180 [Baltic2016]Cities


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,