关于这题费用流写法

P4016 负载平衡问题

@[ningago](/user/371968) 建图距离算错了,不应该是 `min(abs(j - i),abs(i - (j - n)))`。 hack: ```plain input 3 1 2 3 answer 1 ```
by 阿丑 @ 2022-04-27 21:16:33


@[阿丑](/user/364963) 那这个贪心怎么走就会被hack掉呢?
by ningago @ 2022-04-28 11:23:41


@[ningago](/user/371968) 就,算距离那里改成 `min(abs(j - i),n - abs(i - j))` 应该就对了 因为 $i>j$ 时原来那个式子一定会得到 $i-j$,在上面那个 hack 中 3 号点和 1 号点的距离就会算成 $3-1=2$,而实际上应该是 $n-(3-1)=1$。
by 阿丑 @ 2022-04-28 11:31:13


@[阿丑](/user/364963) 过了,就是 $j-i<0$ 出了问题,蟹蟹dalao ~~错成这样82pts珂海星~~
by ningago @ 2022-04-28 11:35:48


考谷,同时谢谢大佬
by best_brain @ 2023-12-29 15:54:35


|