01分数规划

· · 个人记录

01分数规划的大概就是答案有\frac{\sum\cdots}{\sum\cdots}的形式

由于有分数线的存在，使得贪心被卡，于是二分答案，但是check函数因题而异

例题1:

这道题大意就是找一个环，使得点权和除以边权和最大

首先二分答案，设当前答案为mid，那么

\frac{\sum e[i]}{\sum w[i]} =mid \sum e[i]=(\sum w[i])\times mid

那么如果\sum e[i]-(\sum w[i])\times mid<0的话，区间就可以向右收缩，判断负环即可

例题2:

题目大意就是使\frac{\sum t[i]}{\sum w[i]}最大

还是二分答案，即

\frac{\sum t[i]}{\sum w[i]}=mid \sum t[i] = (\sum w[i])\times mid

那么这个时候每头牛的贡献就是

\sum t[i] - (\sum w[i])\times mid

而又考虑到\sum w[i]不能超过W，因此01背包