本地笔记整理，原文写于 2019/8/22，2019/12/8 上传 \[ %dontshow \newcommand{\dpa}{\mathrm{dp}} \newcommand{\len}{\mathrm{len}} \newcommand{\stf}{\mathrm{dp_{forest}}} \]

斯坦纳树是生成树的推广形式，只要求所有顶点的一个子集联通即可。

最小斯坦纳树

一般的所求的都是最小斯坦纳树问题，使用状压 DP 解决。定义 \(\dpa[i][S]\) 为从 \(i\) 点出发，与 \(S\) 集合当中的点保持联通的最小代价。首先我们有子集转移： \[ \dpa[i][S] = \min_{T\subset S}\left\{\dpa[i][T]+\dpa[i][S\setminus T]\right\} \]

但是这样有些边就会被多算，因此在这一步过后还要加上转移： \[ \dpa[i][S] = \min\left\{\dpa[i][S], \min_{i \to j} \left\{\dpa[j][S]+\len[i\to j]\right\}\right\} \] 这个转移就有后效性，但是可以使用 SPFA 解决。

最小斯坦纳森林

最小斯坦纳森林是最小斯坦纳树的升级版本，要求构造一棵最小权森林使得每一类顶点之间两两连通。

定义 \[ \stf[S]=\min_{i\in V}\left\{\dpa[i][S]\right\} \] 表示 \(S\) 中节点都在一棵树上的最小值。

然后由类似的转移： \[ \stf[S] = \min_{T\subset S}\left\{\stf[T]+\stf[S\setminus T]\right\} \] 但是注意，转移时的 \(S\) 和 \(T\) 要满足某一个种类的节点要么都在，要么都不在。