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
最优比率生成环
问题
图上有点权和边权,求一个回路使得点权和比边权和最大
思想
把边权看做花费，点权看做收入。
然后二分答案建图，判正环。
判正环可以转化为权值取负判负环。