Shichikuji and Power Grid - 洛谷
-
首先这题显然不可能是 dp
-
我们发现第二个式子是困难的，但题目竟然给 \(n \leq 2000\) ，因此我们考虑抽象建图。我们把两个点的贡献两两建成一张图，最终的答案显然是把这个图划分成若干个子图，答案就是他们子图的 最小生成树之和 \(+\) 子图中 \(\min c_i\)
-
但我们显然是不可能枚举每个点在哪个集合中的。我们不妨建一个额外点 \(0\) ，让所有点和 \(0\) 连一条长为 \(c_i\) 的边，最后整个图的 MST 即为答案
-
最终复杂度 \(O(n^2 \log n^2)\) ，但使用 Prim 算法可以做到 \(O(n^2)\)