P4784 [BalticOI 2016] 城市 (Day2) 小结

这个题目如果不是模板题的话有点好，可是他是模板。

这个题其实是我随机跳题跳到的。

我看到他的 k<=5 我觉得很奇怪，然后画了一下 k=3,4,5 的所有情况。

然后我就发现这个复杂度是 \(O(n^{\max(1,k-2)})\) 的。很不好。

然后我就想到因为这个 k 很小是不是能用一些奇怪的 dp 来求。

但是我推了好几次都是错的。

后来我发现这个问题其实是最小斯坦纳树。

然后我就学了一下就做完了。

其实 dp 是正确的，只需要记录当前在哪个点，然后集合是什么就可以了。