CF1305G Kuroni and Antihype

发表于 分类于 ， ， 阅读次数：

题意：有一张图，有 个点，点有点权 。

之间存在无向边当且仅当 。

接下来不断执行如下两个操作之一 ：

  • 将一个没有染色的点 染色。

  • 若一个未染色点 和某个染色点 直接相连，将 染色，并获得 元。

当所有点都被染色，操作停止。问能获得的钱数最大值。

，时限 。

在操作二中让 连边，即得到一棵生成森林。

为了避免讨论，新建一个点 ，且初始时就被染色。这样就只用考虑操作二，且产生的是一整棵生成树。

但是，操作的收益和点权有关，不能直接转化成最小生成树。

将 边权写成 ，不难发现最后每个 都被多算了恰好一次，减去即可。

  • ：

由于连边条件， 边权是两个不交集合的并。

枚举边权 ，再枚举子集 ，在 之间连边。这样一共会产生 条边。

（注意，点权相同的点要批量处理）

从小到大枚举边权跑 ，在边多点少时并查集的复杂度是线性的，所以复杂度为 ，已经可以通过。

  • ：

当然还有更好的做法，考虑 算法，每一轮，我们要对每个连通块找到最小出边(到达其他连通块)。

按照套路，每一轮都做一个子集和 （FMT），求出每个集合内连通块编号互异的点权最大值和次大值。

然后，对于某个点 ，查看集合 中的最大值，若和自己同一个连通块，则选择次大值。

每一轮的复杂度是 的，共 轮，总复杂度即为 。