题解 P6192 【【模板】最小斯坦纳树】

最小斯坦纳树，就是要花费最小的代价，连通给定的 $k$ 个关键点，这是一个组合优化问题。 这个问题可以用状压 DP 来解决，首先容易发现一个结论： **答案的子图一定是树。** 证明：如果答案存在环，则删去环上任意一条边，代价变小。 于是我们为这棵树钦定一个树根，设 $dp(i,S)$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小代价。 考虑如何不重不漏地转移。 一棵以 $i$ 为根的树有两种情况，第一种是 $i$ 的度数为 $1$，另一种是 $i$ 的度数大于 $1$。 对于 $i$ 的度数为 $1$ 的情况，可以考虑枚举树上与 $i$ 相邻的点 $j$，则： $$dp(j,S)+w(j,i)\to dp(i,S)$$ 对于 $i$ 的度数大于 $1$ 的情况，可以划分成几个子树考虑，即： $$dp(i,T)+dp(i,S-T)\to dp(i,S)\ \ (T\subseteq S)$$ 这里的转移顺序是有讲究的，这可以理解成一个类似背包的 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)$。