题目链接：

思路：之前做过最小比率生成树，也是属于0/1整数划分问题，这次碰到这道最优比率环，很是熟悉，可惜精度没控制好，要不就是wa,要不就是tle，郁闷啊！实在是懒得码字，直接copy吧：

题目的意思是：求一个环的{点权和}除以{边权和}，使得那个环在所有环中{点权和}除以{边权和}最大。

令在一个环里，点权为v[i]，对应的边权为e[i]，

即要求：∑（i=1，n）v[i]/∑（i=1，n)e[i]最大的环（n为环的点数），

设题目答案为ans，

即对于所有的环都有 ∑（i=1，n）（v[i]）/∑（i=1，n)（e[i]）<=ans

变形得ans* ∑（i=1，n）（e[i]）>=∑（i=1，n）（v[i]）

再得 ∑（i=1，n）（ans*e[i]-v[i]） >=0

稍分析一下，就有：

当k<ans时，就存在至少一个环∑（i=1，n）（k*e[i]-v[i]）<0，即有负权回路(边权为k*e[i]-v[i])；

当k>=ans时，就对于所有的环∑（i=1，n）（k*e[i]-v[i]）>=0，即没有负权回路。

然后我们就可以使新的边权为k*e[i]-v[i]，用spfa来判断付权回路,二分ans。