斯坦纳树
斯坦纳树
对于图$G=(V,E)$，存在子集$K \subset V$，$K$中的点称为关键点。斯坦纳树表示总边权最小的树，仅包含来自$G(V,E)$中的顶点和边，并包含所有关键点。
如果$V=K$，那么问题就变成了熟悉的最小生成树问题，这时候可以采用kruskal或prim算法来解决，时间复杂度为$O(E\log_2{V})$。
如何计算斯坦纳树是一个NP问题，即你无法在多项式时间内求解。但是如果已知$K$非常小，我们可以在关联于$3^K$的一个时间复杂度内利用动态规划解决这个问题。
首先，我们需要意识到斯坦纳树，也是一株树，树必然有根，我们可以枚举根来进行计算。并且由于我们仅关心关键点是否包含在树中，因此我们对关键点进行状态压缩，共$2^K$种状态，我们可以利用二进制来表示。
我们记$dp(i,s)$表示以$i$为根，$i$可以是普通点也可以是关键点，满足$s$代表状态的子树。我们记结点$u$的掩码为$u.mask$，如果$u$是关键点，则$u.mask$表示$u$在二进制中对应的比特位，否则$u.mask$为0。
考虑到对于某一株树的根结点，根结点下有三种情况：
- 根结点没有子结点
- 根结点有一个子结点
- 根结点有多个子结点
因此我们也可以根据三种情况建立状态转移公式。
- $dp(i,s)= s == i.mask ? 0 : \inf$
- $dp(i,s|i.mask)= \min(dp(i,s|i.mask), dp(j,s)+(i,j).w)$
- $dp(i,s)=\min(dp(i,s), dp(i, s' | i.mask) + dp(i, (s - s') | i.mask))$
其中$(i,j).w$表示从$i$到$j$边的权重。
这里稍微说明一下复杂度。总共有$V\cdot 2^K$个$dp$状态，而每个状态根据状态转移公式，时间复杂度如下：
- $O(1)$
- 可以通过在拥有相同状态的dp点上跑SPFA。时间复杂度摊还为$O(E)$，如果边权非负，你还可以利用Dijkstra来将摊还时间复杂度降低到$O(V)$。
- $s$的子集数目为$2^{B(s)}$，其中$B(s)$表示$s$中$1$的数目。由于$\sum_{i=0}^{K}{K \choose i}2^i=(1+2)^K$，因此摊还时间复杂度为$O(1.5^K)$。
因此对于任意一个$dp$状态所需的时间复杂度为$O(V+1.5^K)$，总共有$V\cdot 2^K$个$dp$状态，因此总的时间复杂度为$O(V(V\cdot 2^K + 3^K))$。
斯坦纳森林
斯坦纳森林是由若干斯塔纳树组成的。我们修改一下问题，对于图$G=(V,E)$，存在多个不想交子集$K_1,K_2,\ldots,K_m$，我们称$K_i$中的点称为$i$类关键点。斯坦纳森林是一个总边权最小森林，满足同一类关键点落在相同的树中。
斯坦纳森林可以通过上面的斯坦纳树的动态规划求法获得。假设我们已经获得了上面动态规划结果——dp函数。
我们定义一个新的函数$g$，$g({K_{i_1},K_{i_2},\ldots})$表示包含${K_{i_1},K_{i_2},\ldots}$中所有点，但是不包含${K_1,K_2,\ldots,K_m}-{K_{i_1},K_{i_2},\ldots}$中任意点，且同类关键点落在相同树中的最小边权森林的边权。
我们可以为$g$按照子集关系建立类似递推关系，这里不再赘述，这部分的时间复杂度为$O(3^m+2^K)$。