自动搬运

查看原文

来自洛谷，原作者为

	Milmon HN 高一最菜 OIer | 史上最菜的菜鸡 qaq | 快乐学习，认真刷题，努力进步！

搬运于2025-08-24 22:47:29，当前版本为作者最后更新于2024-07-18 10:11:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提示：本文中所有图片使用 GitHub Pages 托管，如果网络不好可能要使用一些特殊手段才可以看到。

题意

给定一个 $N$ 个岛屿 $M$ 条船的图，每条船双向连接两个岛屿。第 $i$ 个岛屿有一个不安全值 $S_i$。

每时每刻有若干守卫出现在船上，并且必须满足安全法则：对于任意岛屿，停靠在其旁边的船的守卫数量均不少于它的不安全值。

而守卫的分配必须满足：对于任意起点 $s$ 和终点 $t$，从 $s$ 到 $t$ 存在一种经过若干条船的方案，使得每时每刻船上守卫的数量均满足安全法则。在一个岛屿，守卫可以自由地从某个岛屿停靠的一条船来到该岛屿停靠的另一条船。

你需要对于任意的 $k$（$0 \leq k \leq Q$），给图中增加 $k$ 条船并取消一部分船使得岛屿之间仍然连通，船连接的两个岛屿可以任意分配。你需要最小化所需要的守卫数量总和并求出这个值。

子任务 1

先考虑 $1 \leq S_i \leq 2$，$Q = 0$，且所有船形成一条链的情况。在 $Q = 0$ 时，我们只需要考虑守卫的分配即可。

显然每时每刻每艘船的守卫数量都至少为 $1$。不妨令全局减少一个守卫，即 $S_i$ 变为 $0$ 或者 $1$。注意到如果一个岛屿的不安全值变为 $0$，那么这个岛屿可以直接忽略（因为船到达这个岛屿不影响船上的守卫数量，也不可能产生船无法通行的情况），并且连续的船可以视为一条。

此时链上所有岛屿的不安全值均为 $1$，那么只需要为所有船再分配一个守卫即可。

注：图中圆圈表示一个岛屿，其中数字表示不安全值；蓝色的图形表示船，其中数字表示当前方案为其分配的守卫数量。

子任务 2

考虑去掉 $1 \leq S_i \leq 2$ 的限制，这时思路是类似的，每次找出不安全值最小的岛屿，就可以全局减去这个值并统计答案，并忽略一部分不安全值变为 $0$ 的岛屿。

根据上图观察可以发现，非两端的位置 $i$（$1 < i < N$）会对答案产生 $S_i$ 的贡献。此外，最后剩下的一个最大值会对答案产生额外第一份贡献。所以此时的答案就是 $\sum\limits_{i=2}^{n-1} S_i + \max\limits_{i=1}^n S_i$。

子任务 3

考虑把上述做法推广到所有船形成一棵树的情况。

取出不安全值最小的一个岛屿之后，仍然按照之前的做法全局减去这个最小值并计算对答案的贡献。这时候要注意的一点是，该岛屿相连的船需要被合并为同一条船，这条船可以使 $d(i)$ 个岛屿两两连通，在后面的计算中也只会对答案产生一次贡献。

于是只需要维护当前船的数量即可。把岛屿按照不安全值从小到大排序依次处理，设船的数量为 $C$，则每次对答案的贡献为 $C \times (d(u) - 1)$，并把当前船的数量减去 $d(u) - 1$ 条即可。

把贡献平摊到所有岛屿上，容易发现岛屿 $u$ 会对答案产生 $(d(u) - 1) \times S_u$ 的贡献。以及最后剩下的最大值会对答案再次产生一份贡献。

子任务 4

现在忽略给定的船形成一棵树的条件，那么我们就需要取消一部分的船。因为少取消一条船就会使得守卫数量更大，所以此时存在一种最优秀的方案只需要考虑一棵生成树。

考虑怎么找出这样一棵生成树。考虑把子任务 3 中的答案式进行转化，把贡献转化到边上，即 $\sum\limits_{(u,v) \in E}(S_u + S_v) - \sum\limits_{i=1}^n S_i + \max\limits_{i=1}^n S_i$。于是我们只需要令边权为两个端点的 $S$ 值的和，求出最小生成树即可。

子任务 5 & 6

接下来考虑 $Q \neq 0$ 的情况。这时需要加上 $k$ 条边，然后选出一个最小生成树。从 $k = k_0$ 变为 $k = k_0 + 1$ 时，加上的边变多了一条。

显然 $k$ 的值从 $k_0$ 变为 $k_0 + 1$ 时，一定存在一种最优秀的方案只需要修改 $k = k_0$ 时最优解的一条边。

于是只需要每次贪心地找出最优秀的修改方案即可。以 $S$ 值最小的结点为根进行深度优先搜索，钦定一条边为删掉的边，那么需要加上的边的一个端点一定是根结点，另一个端点必须在删掉的边对应的子树中，找出子树中 $S$ 值最小的结点即可。时间复杂度 $\Theta(n^2)$。

子任务 7

考虑优化，把整个过程倒过来做。初始状态显然是以 $S$ 值最小的结点为中心的菊花图，接下来每次删除一条边再加上一条原图中给定的边。

每次删除一条边，整个图变为两个连通块，只需要找一条原图中连接这两个连通块的边权最小的边添加即可。具体实现可以对每个结点维护一个 std::priority_queue 表示还未与该结点合并的结点中，原图中的边的边权以及对应的另一个结点编号。再维护一个 std::set 表示所有连通块之间加边删边的净贡献。使用并查集维护连通块，合并时使用启发式合并即可做到时间复杂度 $O(n \log^2 n)$。