斯坦纳树小记

斯坦纳树问题

平面上有一些点，其中一些是关键点。给出一些点之间的线段，选择一些线段连通这些关键点并且线段总长度最小。

最小斯坦纳树——在图论中的运用

一张无向连通图，选择一个部分结点的生成树，结点包含点集 \(S\)，求生成树的最小边权和。

\(n\le 100,\space m\le 1000,\space |S|\le 10\)

解决

考虑状压 dp。

设 \(f[S,u]\) 表示选出了包含的关键点集合为 \(S\) 且当前树根为 \(u\) 的最小生成树边权和。

转移比较容易：

• 合并两棵树：\(f[S,u]+f[T,u]\to f[S\cup T,u]\)

• 走向新的根：\(f[S,u]+w(u,v) \to f[S,v]\)

初始化：对于第 \(i\) 个关键点 \(a_i\)，有 \(f[\{i\},a_i]=0\)。

注意第二种转移没有明确状态，需要用最短路。

使用 dijkstra，时间复杂度 \(O(n3^{|S|}+|S|m\log m)\)。