斯坦纳树

大大源码 • 2023年4月24日 pm11:33 • 其他

【算法简介】

斯坦纳树一般用于解决这样一类问题，一个无向图，k个关键点，每个边有边权，求联通这k个点的最小代价

最小生成树可以认为是斯坦纳树的特殊情况

由于k个关键点的要求精确覆盖，只能用状压，所以k一般最多到10，n也不会太大

方法：设F[i][s]表示以i为根的子树内，选择的关键点状态为s的最小代价

外层枚举状态S

然后考虑转移：

1.由自己的其他状态转移来F[i][s]=min{F[i][t]+F[i][s^t]}

2.由其他边走过来F[i][s]=min{F[i][s],F[j][s]+e[j][i]}

第二个式子这种三角形不等式可以spfa转移一下

这个时间复杂度为 $O(3^{k}*n+2^{k}*nm)$

前一半的复杂度是枚举第一种转移，后一半是spfa

这里 $3^{k}$ 是要很好的枚举子集，否则会退化成 $2^{2k}$

也就是不能暴力验证一个集合是否是另一个集合的子集，我们要用一种巧妙的方式构造出来这个子集

for(int s=sta;s;s=(s-1)&sta)

sol.(这个是 $O(2^{2k}*n+2^{k}*nm)$ 的做法)

sol.(这个是 $O(3^{k}*n+2^{k}*nm)$ ，建议用这个当成板子记)

THE END