「WC2008」游览计划 「斯坦那树模板」
斯坦那树百度释义
斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。
即最小斯坦那树即为并非选择所有的结点，而是选择一部分结点，为保证它们连通，且求解最小开销
题解斯坦那树模板
发现直接表示点的存在性没有意义
设函数 $f[i][state]$ 表示：对于点 $i$，其它结点与其连通情况
那么有两种转移
其一、由其子集转移$$f[i][state] = \min\limits_{sub \in state} \{f[i][sub] + f[i][\complement_{state}sub] - value_i\}$$之所以要减去 $value_i$ 是因为会算重
附：枚举子集的方法
1for (int sub = state & (state - 1); sub; sub = (sub - 1) & state)
其二、由相邻当前状态下结点转移$$f[i][state] = \min\limits_{state_p = tru ...
「APIO2013」机器人
首先因为点数不多，可以考虑先在 $4r \times c$ 时间内将每个点朝每个方向可以到达的位置预处理出来，建成图
那么现在容易看出是斯坦那树问题，所以考虑将问题简化一下：
现在给定 $n$ 个不同级别的机器人，将两段级别的机器人合并需要花费 $c_i$，那么将所有机器人合并的最小花费是多少
这个问题显然使用区间 $DP$ 可以解决，那么扩展到斯坦那树上即可
令 $f[l][r][i]$ 表示区间 $l, r$ 的机器人合并后位于位置 $i$ 的最小花费，则有$$f[l][r][i] = \min \{f[l][k][i] + f[k + 1][r][i]\}$$以及$$f[l][r][i] = \min\limits_{p link to i} \{f[l][r][p] + 1\}$$第二个式子直接 $SPFA$ 会超时
但是观察每条边的贡献都为 $1$，所以可以将 $SPFA$ 优化成 $BFS$ 的复杂度
类似堆优化的思想，开两个队列，一个存初始的经过 $f$ 排序的点，一个存被松弛的点，由于边的性质及 $que1$ 经过排序的原因，所以 $que2$ 一定也是按 $ ...