分数规划小结

https://www.zybuluo.com/ysner/note/1262173

定义

给定数列\(\{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\)，然后判图中是否有负环，或者网络流看能否跑出正费用。

题目

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

分数规划小结

原文：https://www.cnblogs.com/yanshannan/p/9535955.html