只 WA 了 #2 的看过来
查看原帖
只 WA 了 #2 的看过来
145355
wsyhb楼主2022/1/24 22:21

虽然翻了 20 页提交记录都没有只 WA #2 的,但还是说明一下这个错误。(万一之后有人跟我犯一样的错呢)

一种建图方式是:

  1. 将一个位置 (a,b)(a,b) 拆成两个点 x(a,b)x(a,b)y(a,b)y(a,b)
  2. y(a,b)y(a,b)x(a+1,b)x(a+1,b)x(a,b+1)x(a,b+1) 连边,流量为 nn,费用为 00
  3. (a,b)(a,b) 不为障碍,则由 x(a,b)x(a,b)y(a,b)y(a,b) 连边,流量为 nn,费用为 00
  4. (a,b)(a,b) 为石块,则由 x(a,b)x(a,b)y(a,b)y(a,b) 连边,流量为 11,费用为 1-1。(取相反数转最小费用最大流)

如果你使用这种建图方式,并以 x(1,1)x(1,1) 为源点,以 y(p,q)y(p,q) 为汇点,就会 WA #2,获得 84 分的好成绩。

错误原因:若 (1,1)(1,1) 为石块,则建出的网络相当于有 n+1n+1 个小车。

一个简洁的错误例子:见这个剪贴板。(原本这是拿来 Hack DP 的,结果正好可以卡这个)

2022/1/24 22:21
加载中...