BZOJ 5180 [Baltic2016]Cities

发布于 2018-03-14  146 次阅读


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

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


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

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

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

 


一个非常弱的准退役OIER