最⼩斯坦纳树学习笔记定义摘⾃百度百科的定义：斯坦纳树问题是组合优化问题，与最⼩⽣成树相似，是最短⽹络的⼀种。
最⼩⽣成树是在给定的点集和边中寻求最短⽹络使所有点连通。
⽽最⼩斯坦纳树允许在给定点外增加额外的点，使⽣成的最短⽹络开销最⼩。
可以这么理解：⼀个图的⽣成树是构造⼀棵树把所有点给联通，⽽斯坦纳树则是构造⼀棵树把给定的⼏个点联通。
如同⽣成树有最⼩的⼀棵，斯坦纳树也有最⼩的。
如何求最⼩斯坦纳树，是我们今天要探讨的话题。
实现例题：Luogu P6192【模板】最⼩斯坦纳树给定⼀个包含n个结点和m条带权边的⽆向连通图G=(V,E)。
再给定包含k个结点的点集S，选出G的⼦图G′=(V′,E′)，使得：S⊆V′G′为连通图；E′中所有边的权值和最⼩。
你只需要求出E′中所有边的权值和。
n≤100,m≤500,k≤10。
求最⼩斯坦纳树，我们使⽤的是状压DP。
⾸先⾮常显然的是，这个选出来的⼦图G′⼀定是个树。
令f i,S表⽰当前这个树的根为i，选出的点的集合为S（注意这⾥选出的点专指那k个点中的点），这⾥的S在 dp 中是被状压的。
第⼀种转移⽅式：f i,S=f i,T+f i,S−T (T⊆S)这种转移⽅式意义在于把⼀个根可能会连出多棵S互不相交的树，该⽅程可以合并它们。
此时这个根的度数≥1。
以下是⼀个⽰意图，其中 5,6,7 三个点属于⽬标的那k个点，3 是⽬前的i。
第⼆种转移⽅式：f i,S=f j,S+w(i,j)这种转移⽅式意义在于把⼀个根的状态转移到与他相邻的⼀个根上。
此时根i的度数=1。
⽰意图如下，其中i=1，j=3，S={5,6}，橙⾊虚线代表待扩展的边 (i,j)。
Processing math: 100%考虑 dp 顺序，显然S从⼩到⼤枚举即可。
对于第⼀种转移⽅式，只需枚举S的⼦集T。
对于第⼆种转移⽅式，注意到这玩意⼉是个三⾓不等式，联想到最短路也是如此——没错，⽤最短路跑⼀遍就⾏了。
参考代码int n, m, k, f[Maxn][1 << Maxk];struct Edge {int next, to, dis;}edge[Maxm * 2];int head[Maxn], edge_num;void add_edge(int from, int to, int dis) {edge[++edge_num].next = head[from];edge[edge_num].to = to;edge[edge_num].dis = dis;head[from] = edge_num;}queue <int> Q; int dist[Maxn]; bool inq[Maxn];void SPFA(int S) {memset(inq, 0, sizeof(inq));for(int i = 1; i <= n; ++i) {dist[i] = f[i][S];if(dist[i] != 1061109567) Q.push(i), inq[i] = 1;}while(Q.size()) {int u = Q.front();Q.pop();inq[u] = 0;for(int i = head[u]; i; i = edge[i].next) {int v = edge[i].to;if(dist[v] > dist[u] + edge[i].dis) {dist[v] = dist[u] + edge[i].dis;if(!inq[v]) {inq[v] = 1;Q.push(v);}}}}for(int i = 1; i <= n; ++i) f[i][S] = dist[i];}int main() {n = read(); m = read(); k = read();int u, v, w;for(int i = 1; i <= m; ++i) {u = read(); v = read(); w = read();add_edge(u, v, w);add_edge(v, u, w);}memset(f, 63, sizeof(f));for(int i = 1; i <= k; ++i) {u = read();f[u][1 << (i - 1)] = 0;}for(int i = 1; i <= n; ++i) f[i][0] = 0;for(int S = 0; S < (1 << k); ++S) {for(int i = 1; i <= n; ++i)for(int T = S & (S - 1); T; T = S & (T - 1))f[i][S] = min(f[i][S], f[i][T] + f[i][T ^ S]);SPFA(S);}int ans = 2e9;for(int i = 1; i <= n; ++i) ans = min(ans, f[i][(1 << k) - 1]);cout << ans << endl;return 0;}例题[WC2008] 游览计划考虑把每个⽅格当成⼀个点，最⼩斯坦纳树搞它就完了。
