模板及讲解
推荐入门文章
分数规划就是求$\sum A_i / \sum B_i$最大/最小。
$\sum A_i / \sum B_i$最大/最小问题
我们设$C(x)$为$\sum A_i / \sum B_i \geq x$是否成立
(或者是$\sum A_i / \sum B_i \leq x$)
$\sum A_i / \sum B_i \geq x$
去分母$ \sum A_i \geq \sum B_i \times x$
移项$\sum A_i - \sum B_i \times x \geq 0$
合并同类项$\sum (A_i - B_i \times x) \geq 0$
那么我们进行二分，每次二分一个$x$，如果$C(x)=true$，那么$l=mid$，否则$r=mid$
$C(x)$的计算就是把$(A_i - B_i \times x)$排序，取最大的那几个
最优比率生成树
进行二分，每次二分一个$x$，每条边的边权设为$A_i - B_i \times x$，然后跑MST检验答案即可(根据$\sum (A_i - B_i \times x) \geq 0$)。
最优比率环
进行二分，每次二分一个$x$，每条边的边权设为$A_i - B_i \times x$，然后DFS版的SPFA检测是否存在正/负环(根据$\sum (A_i - B_i \times x) \geq 0$)
常见题型：
1、$\sum A_i / \sum B_i$最大/最小问题
Q：见解析
解：见解析
例题：poj 2976
2、最优比率生成树
Q：见解析
解：见解析
例题：poj 2728//强行Prim不想写……明年再说吧qaq
3、最优比率环
Q：见解析
解：见解析
例题：Bzoj 1960
