虽然翻了 20 页提交记录都没有只 WA #2 的,但还是说明一下这个错误。(万一之后有人跟我犯一样的错呢)
一种建图方式是:
- 将一个位置 (a,b) 拆成两个点 x(a,b) 和 y(a,b);
- 由 y(a,b) 向 x(a+1,b) 和 x(a,b+1) 连边,流量为 n,费用为 0;
- 若 (a,b) 不为障碍,则由 x(a,b) 向 y(a,b) 连边,流量为 n,费用为 0。
- 若 (a,b) 为石块,则由 x(a,b) 向 y(a,b) 连边,流量为 1,费用为 −1。(取相反数转最小费用最大流)
如果你使用这种建图方式,并以 x(1,1) 为源点,以 y(p,q) 为汇点,就会 WA #2,获得 84 分的好成绩。
错误原因:若 (1,1) 为石块,则建出的网络相当于有 n+1 个小车。
一个简洁的错误例子:见这个剪贴板。(原本这是拿来 Hack DP 的,结果正好可以卡这个)