Processing math: 100%
斯坦纳树

斯坦纳树

dp[i][S]表示 当前根为i当前生成树已经覆盖掉得关键点集合是S得最小代价。

转移分两种:

  • 合并同一个根下的两种状态,dp[i][S1|S2]=min(dp[i][S1]+dp[i][S2]w[i]),S1&S2=0

  • 通过一个点状态转移到其他点的这个状态,就是选择一个点把根置成它

    dp[j][S]=min(dp[i][S]+w[j])

转移的顺序是从小到大枚举集合,枚举所有点跑第一种转移,然后对这个状态跑第二种转移。

注意到这里没有必要判断j是否为关键点,如果它是关键点,在前面第一种转移中一定已经转移过了(除开这个点必然会剩下一个更小的集合,这个集合是已经被计算了的)。

复杂度是n3n

没有代码

文章作者: yijan
文章链接: https://yijan.co/old32/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog