Earthquake

每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。

来源 Luogu P4951 · 标签 生成树 / 二分答案 / 分数规划 / Kruskal

题目描述

有 𝑛 个牧场和 𝑚 条可修建的双向道路。第 𝑖 条道路连接 𝑢𝑖,𝑣𝑖,成本为 𝑐𝑖,施工时间为 𝑡𝑖。约翰支付 𝑓 元,要求选择若干道路把所有牧场连通。

奶牛获得的单位时间利润为

𝑝=𝑓−∑𝑖∈𝑆𝑐𝑖∑𝑖∈𝑆𝑡𝑖

其中 𝑆 是修建的道路集合。求 𝑝 的最大值。若无法盈利,输出 0.0000。

1≤𝑛≤400,1≤𝑚≤10000,1≤𝑓,𝑐𝑖,𝑡𝑖≤2×109。

题解

二分答案 𝑝。对当前值 𝑥,条件

𝑥≤𝑓−∑𝑐𝑖∑𝑡𝑖

等价于

𝑓≥∑(𝑐𝑖+𝑥𝑡𝑖)

因此把每条边的权值改为 𝑤𝑖(𝑥)=𝑐𝑖+𝑥𝑡𝑖,求最小生成树的权值和。若最小生成树权和不超过 𝑓,则 𝑥 可行,答案可以更大;否则缩小 𝑥。

用 Kruskal:每轮重新计算边权并排序,并查集维护连通性。二分到精度满足四位小数输出即可。若 𝑥=0 都不可行,输出 0.0000。

复杂度

每次判定需要排序和 Kruskal,复杂度 𝑂(𝑚log𝑚);二分次数为 𝑂(log𝜀−1),总复杂度 𝑂(𝑚log𝑚log𝜀−1),空间 𝑂(𝑛+𝑚)。

源码位置