【bzoj 3232】圈地游戏(算法效率--01分数规划+图论--最小割)

题目:DZY家的后院有一块地,由N行M列的方格组成,格子内种的菜有一定的价值,并且每一条单位长度的格线有一定的费用。DZY喜欢在地里散步。他总是从任意一个格点出发,沿着格线行走直到回到出发点,且在行走途中不允许与已走过的路线有任何相交或触碰(出发点除外)。记这条封闭路线内部的格子总价值为V,路线上的费用总和为C,DZY想知道V/C的最大值是多少。

解法:要求 v/c 的最大值,就是01分数规划了。普遍解法就是二分它的答案值,在这个答案值的条件下选最佳的策略,再判断是否合法以及是否有更优的解。而本题的寻找最优策略的方法就是转化为图,求最小割。

具体来说,就是我们要求 v/c 的最大值,可以把它化成 x=v/c,要使 x 最大。另设 f(x)=v-c*x ,对于固定的(此时最优的) v 和 c,若 f(x)≥0,说明 x 还可以有更优的解,便继续二分。而对于此时最优的 v 和 c,也就是在枚举 x 时,用 v,c 使 f(x) >0

P.S.代码我没有时间打了。。。QwQ

上一篇:zoj 2676 Network Wars 0-1分数规划+最小割


下一篇:【算法】01分数规划 --- HNOI2009最小圈 & APIO2017商旅 & SDOI2017新生舞会