bzoj 4819: [Sdoi2017]新生舞会 费用流

(a1 + a2 + …… + an) / (b1 + b2 + …… + bn) == c尽可能大

我们移项  a1 + a2 + ……+ an = cb1 + cb2 + …… + cbn

然后我们接着移项 (a1 – cb1) + (a2 – cb2) + …… + (an – cbn) = 0

我们考虑二分这个c,即二分答案。然后我们希望c尽可能大。 即如果发现当前算完的左式的最大值小于0,那么意味着c有些大了。如果左式的最大值大于0,那么意味着c有些小了。那么我们可以二分。

那么我们怎么求这个式子的值呢。最大流量最大费用流。就是说我们把边都建成负数,然后跑的结果取反就可以了。

发表评论