给 MLE 63 分的提个醒
查看原帖
给 MLE 63 分的提个醒
118196
zimujun楼主2021/8/19 10:20

如果您是用的 zkw 费用流(dinic 实现)

  • 数据范围中 0ci0 \le c_i,在 dfs 的过程中可能会出现 00 环,因此您的代码在 dfs 的过程中可能会出现无限递归而 MLE,请记一个数组来标记某个点是否还在搜索栈中,这里可以直接用 spfa 时的 inqueue 数组,因为最短路跑完之后这个数组一定都是 false

  • 另外还有一个误区,在跑最短路的时候一定不要搜到汇点就返回,这样并没有充分完成松弛操作,求得的最短路不一定是最短的。要求完所有的最短路。

2021/8/19 10:20
加载中...