斯坦纳树

Posted on 2019-12-08 Edited on 2022-06-14 Views:

本地笔记整理，原文写于2019/8/22，2019/12/8上传

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

最小斯坦纳树

一般的所求的都是最小斯坦纳树问题，使用状压DP解决。定义 $\dpa[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\}$

表示

中节点都在一棵树上的最小值。

然后由类似的转移：

$\stf[S] = \min_{T\subset S}\left\{\stf[T]+\stf[S\setminus T]\right\}$

但是注意，转移时的

和

要满足某一个种类的节点要么都在，要么都不在。