arc026_4 题解

翻译：

有 个村庄，编号从 到 。这些村庄通过 条道路构成一个连通图。

有一天，一场大规模的灾难摧毁了所有的道路，使得村庄之间的交通无法进行。你需要修复一些道路，将这几个村庄连接起来。

您首先估计了修理每条道路所需的费用和时间。然后计算出最低小时工资。

「小时工资」是指「修路所需费用的总和」除以「工作总时长（单位：小时）」，即

请注意，不一定要修理所有的道路，也可以修理不需要的道路，只要将村庄连接起来即可。

保证图联通，且没有自环，重边。

根据题目的描述，一条边对 的贡献的多少，可以用 衡量吗？

也许，在一定程度上，是可以对比两条边的贡献。

于是，一开始我便想到一种做法，选择所有 的边，剩余的边再以 比较跑最小生成树。

能保证正确性的一个显然的结论是： 的所有边总对于贡献为负。（就是能够让 尽可能小）

但是，这显然是错的。反例：对于一条边 ，

为什么？有一条式子（不妨 ，等号同时取）：

代入到 的变化，同时设 ，条件是 （同 ）。

由于题目并未保证 ，所以有可能有 。

所以有：

观察到 （结果变大了，贡献非负）。

所以并不是所有 的边都对贡献为负，还需要判断当前 与 的大小关系等。

考虑到这不好维护，转换以下思路。

不能够通过 来判断边之间的贡献情况。注意到 ，可以容下 。

如何将判断贡献转换为整式的判断呢？

考虑二分最终 。

但是，我们如何判断一个 （简称为 ） 是否能够被构造出来呢？

由于我们的目标是判断是否能构造 。

，

那么，处理为整式之后，只需要判断当前选择 之和是否小于等于 即可。

通过这个变换可以将判断目标变为正负代价的简单判断。

对于每一条边，我们让 整合代价 。

若 为负，必然对最终的总代价是好的（目标是非正数嘛）。

那么就可以对边按 排序，选完所有 非正的，最终对正数跑最小生成树即可！

如果跑出的生成树结果与之前选择负数贡献边的贡献之和小于等于 ，那么必然可以构造！

注意！这里的判断只能判断对应 能否构造出更小的结果（即只能获得上下界信息），所以才只能二分。

时间复杂度：。（）