斯坦纳树
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。
没有代码