http://poj.org/problem?id=3621
题意:
给定一张图,边上有花费,点上有收益,点可以多次经过,但是收益不叠加,边也可以多次经过,但是费用叠加。求一个环使得收益和/花费和最大,输出这个比值。
思路:(转载)
首先的一个结论就是,不会存在环套环的问题,即最优的方案一定是一个单独的环,而不是大环套着小环的形式。这个的证明其实非常的简单,大家可以自己想一下(提示,将大环上的收益和记为x1,花费为y1,小环上的为x2,y2。重叠部分的花费为S。表示出来分类讨论即可)。有了这个结论,我们就可以将花费和收益都转移到边上来了,因为答案最终一定是一个环,所以我们将每一条边的收益规定为其终点的收益,这样一个环上所有的花费和收益都能够被正确的统计。
解决了蛋疼的问题之后,就是01分数规划的部分了,我们只需要计算出D数组后找找有没有正权环即可,不过这样不太好,不是我们熟悉的问题,将D数组全部取反之后,问题转换为查找有没有负权环,用spfa或是bellman_ford都可以。这道题目就是典型的不适合用Dinkelbach,记录一个负权环还是比较麻烦的,所以二分搞定。
上面讲的挺清晰的。。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include