斯坦纳树

Summary

最小斯坦纳树在带权无向图中连接给定的必选点，可以借助其他点降低总边权。必选点较少时，固定一个必选点作为最终的根，用状态压缩动态规划维护其余必选点的子集。转移在同一顶点合并两个子集，再沿最短路移动根。P6192 用 Floyd 预处理全源最短路，并用三角不等式保证移根转移可以原地更新。

参考资料

• 斯坦纳树 - OI Wiki

简介

给定边权非负的无向连通图 $G=(V,E)$ 和必选点集 $S\subseteq V$，求包含 $S$ 的边权和最小的连通子图。删去环上的边不会增大边权和，因此可以取一棵树，称为 最小斯坦纳树（Minimum Steiner Tree）。

树中可以包含 $S$ 之外的点。例如，三个必选点两两之间的边权均为 $2$，另有一个点到三者的边权均为 $1$。只用必选点的最小代价为 $4$，加入这个点后只需 $3$。当 $S=V$ 时，问题退化为 最小生成树；当 $S$ 只有两个点时，答案就是两点间的 最短路 长度。

状态压缩动态规划

任选一个必选点 $r$，记其余必选点的集合为 $T$。设 $f_{A,u}$ 为连接子集 $A\subseteq T$ 和顶点 $u$ 的最小代价，答案为 $f_{T,r}$。空集的代价为 $f_{\varnothing,u}=0$。

记 $g_{A,x}$ 为在同一个点 $x$ 合并两个非空子集的最小代价：

$$g_{A,x}=\min_{\varnothing\ne B\subsetneq A}(f_{B,x}+f_{A\setminus B,x})$$

若 $A$ 只有一个点，则在该点令 $g_{A,x}=0$，其他位置为 $\infty$。记 $d_{x,u}$ 为 $x$ 到 $u$ 的最短路长度。合并后沿最短路移根：

$$f_{A,u}=\min_{x\in V}(g_{A,x}+d_{x,u})$$

对多点集合，取一棵所有叶子都属于 $A$ 或为 $u$ 的最优树。从 $u$ 沿唯一的分支走到首个属于 $A$ 的点或分叉点 $x$，也可能一开始就有 $x=u$。若 $x\in A$，将 $x$ 单独分为一组；否则将 $x$ 的分支分为两组。两组子树与 $u$ 到 $x$ 的路径互不重边，所以转移能覆盖最优解。反过来，两棵子树与最短路的并集连通且包含 $A$ 和 $u$，实际代价至多为转移式中的和。

用 Floyd 预处理 $d$，再按掩码递增顺序处理子集。枚举划分时固定最低位所在的一侧。移根可原地更新：由三角不等式，经多个点移根不会优于直接移根。设 $n$ 为点数、$k$ 为必选点数，读入后的时间复杂度为 $O(n^3+n3^{k-1}+n^22^{k-1})$，空间复杂度为 $O(n^2+n2^{k-1})$。若图较稀疏，也可将 $g_{A,x}$ 作为各点的初始距离，用多源 Dijkstra 完成移根。

例题

洛谷 P6192 【模板】最小斯坦纳树

给定一张 $n$ 个点、$m$ 条边的无向连通图，从中选出一个包含全部 $k$ 个必选点的连通子图，输出最小边权和。图中可能有重边和自环，且 $n\le100$，$m\le500$，$k\le10$，边权为 $1\sim10^6$。