自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:18:24，当前版本为作者最后更新于2020-03-07 23:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最小斯坦纳树，就是要花费最小的代价，连通给定的 $k$ 个关键点，这是一个组合优化问题。

这个问题可以用状压 DP 来解决，首先容易发现一个结论：

答案的子图一定是树。

证明：如果答案存在环，则删去环上任意一条边，代价变小。

于是我们为这棵树钦定一个树根，设 $dp(i,S)$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小代价。

考虑如何不重不漏地转移。

一棵以 $i$ 为根的树有两种情况，第一种是 $i$ 的度数为 $1$，另一种是 $i$ 的度数大于 $1$。

对于 $i$ 的度数为 $1$ 的情况，可以考虑枚举树上与 $i$ 相邻的点 $j$，则：

对于 $i$ 的度数大于 $1$ 的情况，可以划分成几个子树考虑，即：

这里的转移顺序是有讲究的，这可以理解成一个类似背包的 DP，与 $i$ 相邻的点是一个个出现的，每次多合并上一个点，所以按 $S$ 升序枚举即可。

这两种转移具体如何实现呢？对于下面一种较为简单，枚举子集即可，时间复杂度为 $O(n\times 3^k)$，因为 $\sum\limits_{S\subseteq\{1,\ldots,n\}} |S|$ 是 $O(3^n)$ 的。

对于上面一种，其实可以想到最短路模型的三角形不等式，对于每个 $S$，将图做一次松弛操作即可。

由于我不喜欢 SPFA，所以这里采用了 dijkstra 实现，这部分时间复杂度为 $O(m\log m\times 2^k)$。

所以总时间复杂度为 $O(n\times 3^k+m\log m\times 2^k)$。