本文共 661 字，大约阅读时间需要 2 分钟。

斯坦纳树

用途

给一个图，求最小生成树？

这个很简单，prim/kruskal搞一搞。

如果只要求联通某几个点，而不强制要求其他点的联通？

这个prim/kruskal就不好做了。

那怎么求这个呢？

当然是要用到斯坦纳树啊。

计算方法

假设$f_{i,sta}$表示最后一个联通的是$i$，当前要求点的联通性为

1. $f_{i,sta}=f_{i,s}+f_{i,sta-s}$，其中$s$是$sta$的子集。
2. $f_{i,sta}=f_{u,sta}+val_{u,i}$，其中$u,i$之间有边相连。

第一个方程是很好维护的，关键是第二个方程。

观察到，第二个方程与spfa的方程$d_{v}=d_{u}+val_{u,v}$很相似。

那么我们就可以用spfa维护第二个方程啦！

例题

斯坦纳森林

用途

给一个图，求最小生成树？

这个很简单，prim/kruskal搞一搞。

如果只要求联通某几个点，而不强制要求其他点的联通？

这个很简单，斯坦纳树可以解决这个问题。

如果只要求某几个集合中的点互相联通，而分属两个不同集合的点没有要求，可以共用边？

这个就需要用斯坦纳森林了。

计算方法

把所有的集合放在一起，做一遍斯坦纳树，然后对所有集合做一遍子集合并dp。

例题

转载地址：http://eywo.baihongyu.com/