给定一个包含 \(n\) 个点和 \(m\) 条边的无向联通图 \(G=(V,E)\)。
再给定包含 \(k\) 个结点的点集 \(S\)，选出 \(G\) 的子图 \(G‘=(V‘,E‘)\)，使得：
由于要求边权和最小，我们最后得到的一定是一棵树，我们称之为最小斯坦纳树。
一般情况下 \(S\) 的元素个数都非常小，我们考虑用状态压缩，设 \(f[i][s]\) 表示以 \(i\) 为根的至少包含 \(s\) 这个状态的边权最小值。
在一个连通块内部我们可以用子集\(dp\)的方式转移：\(f[i][s]=min(f[i][s],f[i][s‘]+f[i][s\oplus s‘])\)，其中 \(\oplus\) 为异或操作，\(s‘\) 为 \(s\) 的一个子集。
考虑如何扩展连通块（拓展根）：我们把已知的 \(f[i][s]\) 跑一遍多源最短路，就可以得到全部的 \(f[?][s]\) 了。
例题：
原文：https://www.cnblogs.com/With-penguin/p/13290217.html