分数规划小结

总结 分数规划

---

定义

给定数列$\{a\},\{b\}$，求解一组数列$\{x\}$（$x_i=\{0,1\}$)
使得

$$\frac{\sum_{i=1}^na_i*x_i}{\sum_{i=1}^nb_i*x_i}$$
最大化。
（只要有未知量相除，都是这玩意儿）

方法

主要是二分答案。
设二分出的值为$mid$,
则应有

$$\frac{\sum_{i=1}^na_i*x_i}{\sum_{i=1}^nb_i*x_i}\geq mid$$
化化式子
$$\sum_{i=1}^na_i*x_i\geq mid*\sum_{i=1}^nb_i*x_i$$
$$\sum_{i=1}^na_i*x_i-mid*\sum_{i=1}^nb_i*x_i\geq0$$
于是只要找出一组$a_i-mid*b_i\geq0$，就能说明$ans\geq mid$，缩小了二分范围。

实现

一般都是边权设为$a_i-mid*b_i$，然后判图中是否有负环，或者网络流看能否跑出正费用。

题目

• [HNOI2009]最小圈
  $a_i$是边权，$b_i=1$，改下不等号方向，找负环即可。
• [APIO2017]商旅
  把所有能交易的一对集市都连起来，预处理出每对间的距离$b_i$，和可能得到的最大利润$a_i$（即商品最大差价）。
  然后把所有点入队找非负环即可。
  当然如果你入队了却不标记，就会卡在$94pts$卡半年。
• [SCOI2014]方伯伯运椰子
• [SDOI2017]新生舞会
• [bzoj3232]圈地游戏