分数规划

借鉴博客

01分数规划

问题

有一堆物品,每一个物品有一个收益$ai$,一个代价$bi$,我们要求一个方案使选择的$\frac{\sum a_i}{\sum b_i}$ 最大

思想

式子变形后得 $\sum a_i - x \times \sum b_i \geq 0$

那么可以二分$x$, 然后排序check即可。

最优比率生成树

问题

图上每条边有两个权值$cost, len$, 求一个生成树,使得$\frac{\sum cost_i}{\sum len_i} \geq x$

思想

二分答案,每条边的边权变为$cost - x \times len$, 跑最小生成树check

最优比率生成环

问题

图上有点权和边权,求一个回路使得点权和比边权和最大

思想

把边权看做花费,点权看做收入。

然后二分答案建图,判正环。

判正环可以转化为权值取负判负环。

Thank you for your support!