Earthquake
每条边有成本 c 和时间 t,最大化 (f - Σc) / Σt;二分答案后把边权改为 c + p t,用最小生成树判定。来源 Luogu P4951 · 标签 生成树 / 二分答案 / 分数规划 / Kruskal
题目描述
有 个牧场和 条可修建的双向道路。第 条道路连接 ,成本为 ,施工时间为 。约翰支付 元,要求选择若干道路把所有牧场连通。
奶牛获得的单位时间利润为
其中 是修建的道路集合。求 的最大值。若无法盈利,输出 0.0000。
,,。
题解
二分答案 。对当前值 ,条件
等价于
因此把每条边的权值改为 ,求最小生成树的权值和。若最小生成树权和不超过 ,则 可行,答案可以更大;否则缩小 。
用 Kruskal:每轮重新计算边权并排序,并查集维护连通性。二分到精度满足四位小数输出即可。若 都不可行,输出 0.0000。
复杂度
每次判定需要排序和 Kruskal,复杂度 ;二分次数为 ,总复杂度 ,空间 。