01分数规划

· · 个人记录

博客材料录用转载声明：

分数规划的博客

P1570 KC 喝咖啡

设最优答案 \frac{\sum v_i}{\sum c_i}=\gamma

那么 \sum v_i-\sum c_i\gamma=0

也就是说，左边的式子越靠近 0 ，\gamma 的值就越接近最优解，因为 \gamma 具有单调性并且可以发现左边的式子在 \gamma 相同时越大说明 \gamma 可以扩展的更大，所以我们选取 v_i-\gamma c_i 最大的 m 个值即可

如果说推出了 \gamma\sum c_i-\sum v_i=0

这个时候还是要靠近 0 ，只不过这一次我们发现，当 \gamma 相同时，整个式子的值越小说明 \gamma 扩展的空间越大，所以我们选 m 个小值即可

两种方法是等价的

Desert King

题面翻译：给出 n 个点的坐标以及高度，i,j 之间的如果修路那么路的距离为欧几里得距离，修路的花费为 |h_i-h_j| ，求最小比率生成树，即 \frac{cost}{dis} 最小

依旧是分数规划，考虑 \gamma=\frac{cost}{dis} 那么 \gamma dis-cost=0 考虑我们想让 \gamma 最小，那么在 \gamma 相同的情况下，整体的值越大，越想接近 0 那么 \gamma 的值就要越小，所以我们求出最大生成树就可以让 \gamma 尽可能地小，然后二分即可

~POJ的测评太慢了，8.22下午提交的记录一看8.21的提交记录都没测完~

Sightseeing Cows

题面翻译：求最优比率环，并且比率最大

设 \frac{w}{cost}=\gamma ，那么 \gamma cost-w=0 ，考虑最终答案为 k ，想让 \gamma 尽可能大，那么就让整体尽可能小那么如果 \gamma<k 那么 \gamma cost-w<0 也就是说环的权值为负数也就是负环，如果说 spfa 判断出来了负环那么调整 l 否则调整 r 即可

等到学完图论再来补代码