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

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