斯坦纳树
本地笔记整理,原文写于2019/8/22,2019/12/8上传
斯坦纳树是生成树的推广形式,只要求所有顶点的一个子集联通即可。
最小斯坦纳树
一般的所求的都是最小斯坦纳树问题,使用状压DP解决。定义为从点出发,与集合当中的点保持联通的最小代价。首先我们有子集转移:
但是这样有些边就会被多算,因此在这一步过后还要加上转移:
这个转移就有后效性,但是可以使用SPFA解决。最小斯坦纳森林
最小斯坦纳森林是最小斯坦纳树的升级版本,要求构造一棵最小权森林使得每一类顶点之间两两连通。
定义
表示中节点都在一棵树上的最小值。然后由类似的转移:
但是注意,转移时的和要满足某一个种类的节点要么都在,要么都不在。