这是一道 NP-Hard 题。
简化题意
有一个 个点 条有边权旧边和 条无边权新边的无向图，你可以自由决定新边边权，之后对整个图求 MST ，若 MST 不唯一，你可以自由选择任意一颗 MST ，你在节点 上的收益为 到 MST 的根节点的新边边权之和乘以点 的点权。
你需要合理决策，使得所有点的收益之和最大。
我们注意到 非常小，所有最终复杂度极有可能和 相关。
我们先枚举一个新边的集合，将这个集合中的点先加入 MST 中，之后再加入旧边。
根据 MST 的性质，未被加入 MST 的旧边 一定满足： MST 上 、 两点之间的边权均小于等于 。
因此对于每一条没有被加入的旧边 ，我们将 MST 上 、 两点之间所有新边的权值均与 取较小值，作为新的边权。
但是这样的时间复杂度是 的（使用树剖修改），仍然无法通过，可以获得 。
使用人类智慧：图上的很多旧边我们并不关心，我们只用关心会影响新边边权的旧边即可。
考虑缩点：先对原图做一次 MST ，先加入新边，后加入旧边，再把所有新边删除，得到若干的连通块，这些连通块内的所有旧边均不会对答案产生任何影响，可以缩成一个点。
之后再使用上面 的过程即可.
时间复杂度为 ，刚好可以通过。
暂无评论