[图论算法] 斯坦纳树
斯坦纳树解决的是这么一类问题——在图上选择N个节点，求只计算这N个节点的最小生成树。该问题是NP完全的，这意味着它没有多项式时间的解法。一般来说，我们使用状压DP解决这个问题
我们让 表示已经考虑的节点状态为i（如果i的第k位是1，那么我们已经把需要考虑的第k个节点考虑进去了），当前斯坦纳树的根节点为j的解（边权和），那么，显然一棵斯坦纳树可以裂成两个，换句话说：
，其中
，对于这个方程，我们可以采用子集DP的方法解决。同时，如果我要换根操作，那么显然又有
，其中
的意思是k到j的最短路径，但是这个方程有后效性，怎么办？
我们可以贪心一点，对于每个i，选取最小的 ，并记作此时的j是T，并对这种有后效性的状态转移方程，采用单源最短路径的方法转移，算出其他的
，即可求出答案。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！