0/1分数规划
例题 Y329 重建小镇
给定 \(m\) 条边,每条边有边权 \(w_i\) 和 \(t_i\),选出若干条边,要求保证图的连通性,并最大化 $$ \frac{f-\sum_{i\in E'}{w_i}}{\sum_{i\in E'}{t_i}} $$ 其中 \(f\) 是给定的常数,\(E'\) 表示选出的边集。
要想最大化选出物品的价值和选出物品的代价之比,考虑使用二分求解。我们令
$$
\frac{f-\sum_{i\in E'}{w_i}}{\sum_{i\in E'}{t_i}}\ge k
$$
变形:
$$
\sum_{i\in E'}{kt_i+w_i}\le f
$$
我们在 check
函数中将每条边的代价重新设为 \(kt_i+w_i\),跑最小生成树,求出上式的最小值,判断其是否小于 \(f\)。
求分数最值,可以考虑使用二分法。