斯坦纳树
斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。 --du
也就是，n个点，m条边的无向图，最小生成树是要求把n个点都包含在内的最短网络，斯坦纳树是要求至少要把特定的k个点包含在内的最短网络，你可以多包含其他的点。最小生成树可以看成是一种特殊的斯坦纳树。
那么问题已经明确了，这个问题是用状压dp来解决的。所以k一般是很小的，不然状压dp不够用了，，
先看一道板子题。
0 条评论