跳转至

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\)

求分数最值,可以考虑使用二分法。