自动搬运

查看原文

来自洛谷，原作者为

	1kri 寄

搬运于2025-08-24 22:44:02，当前版本为作者最后更新于2023-01-16 21:49:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个显然的事实：最终一定是选中的点不保留出边，未选中的点仅保留一条出边。

我们先只考虑每个点边权最小的出边，这些边连成了一个基环树森林。如果每一棵基环树的环上都有点被选中，那么答案就是未被选中的点在这个基环树森林上出边的边权和。否则，假设我们有一个环没有选中，它会导致所在的基环树中的某些点不合法。此时，我们需要考虑调整一些出边，使得环上的点合法，不难发现这样它所在的基环树的所有点都可以变得合法。

我们可以考虑把整个环缩成一个大点，它的所有出边就是环内连向环外的所有边将边权变为原边权减去原最小出边的边权后的结果。这样缩点后，新的点不选等价于原来一整个环不选，调整这个环等价于连出去一条边，而整个环不选的代价就是调整的代价，也就是某条出边的边权。这样，缩完点后的问题与原问题完全等价，我们可以一直这样做下去，每次缩点后统计新缩的点不选的方案数和代价，直到无法缩点。

在实现时，我们需要支持：找环、缩点和合并边集（需要整体减去某个值）。对于前两项，我们可以用并查集简单维护。合并边集我们可以用 $\text{set}$ 启发式合并，整体修改可以对于每个 $\text{set}$ 打上标记来记录偏移量。时间复杂度 $O(n \log^2 n)$。