01分数规划
什么是01分数规划?
分数规划用来求一个分式的极值。
给出$a_i$和$b_i$,求一组$w_i$ ∈ {0,1},最小化或最大化
$$\frac{\sum_{i=1}^n a_i \times w_i}{\sum_{i=1}^n b_i \times w_i} $$
另一种描述:每种物品有两个权值$a$和$b$,选出若干个物品使得$\frac{\sum a}{\sum b}$ 最大/最小。
在图论问题(求负环、最小生成树和最短路)中类似于$\frac{\sum a}{\sum b}$这样形式的题,称为01分数规划
有什么用?
做图论题会用到
怎么用?
二分
例如 观光奶牛 这道题
判断图中是否存在环$C$,使得$\frac{\sum a}{\sum b} \gt mid$
$\frac{\sum a}{\sum b} \gt mid \Leftrightarrow \sum a \gt mid \times \sum b \Leftrightarrow \sum a - mid \times \sum b \gt 0$
所以公式可以转换为:$\sum(a_i - mid \times b_i) \gt 0) \Leftrightarrow 图中是否存在正环$
01分数规划思路
1. 二分出一个常值
2. 整理不等式,重新定义点权/边权
3. 做图论算法
参考文献:
OI Wiki分数规划