求助:关于 WC2019 中的模拟费用流 ppt
  • 板块学术版
  • 楼主wenhao801
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/5/8 17:59
  • 上次更新2023/11/4 23:32:59
查看原帖
求助:关于 WC2019 中的模拟费用流 ppt
31488
wenhao801楼主2021/5/8 17:59

是经典的老鼠进洞问题!

下面两张图,第一个的题面是“nn 只老鼠,mm 个能容纳一只老鼠的洞,老鼠只能往左走,问全部进洞的最小距离和”,第二个是把老鼠只能往左走去掉。

(我推测那个“xi-x_i 单调递减”应该写成“yi-y_i 单调递减”)

我的问题就出在第二张图的 yiy_i,它是单调递增的,此时为什么还是一定比 f[i1][j]f[i-1][j] 优。。

比如洞所在的位置为 1,7,8,1, 7, 8, \cdots,老鼠所在的位置为 3,5,6,3, 5,6, \cdots 时,f[8][1]f[8][-1] 就应该从 f[7][1]f[7][-1] 转移,而不是从 f[7][2]+8f[7][-2] + 8 转移吧/kel

2021/5/8 17:59
加载中...