警示后人
查看原帖
警示后人
625206
Remilia1023楼主2022/10/16 22:12

INFINF 不能开小了,一开始开成 maxi=1nai\max\limits_{i=1}^n{a_i}, WA 3030,后来发现 flowi=0flow_i = 0 的情况会影响最短路结果,影响正确性,所以 INFINF 不能开小了。

maxi=1nai+100\max\limits_{i=1}^n{a_i} + 100 类似这种也不行,100100 太小了,几次增广之后可能某条边 flowiflow_i 还会变成 00,比较保险的是开成 2×maxi=1nai2\times\max\limits_{i=1}^n{a_i} 以上(我直接 1e15 过了)。

2022/10/16 22:12
加载中...