关于 Dinic 当前弧优化的一个小疑问
查看原帖
关于 Dinic 当前弧优化的一个小疑问
110426
ZnO34楼主2020/8/22 11:38

萌新刚学 OI 当前弧优化,有一点小疑问。

假如有下面这张图,采用当前弧优化之后,会在从点 1 访问到点 3 的时候,遍历点 3 的所有出边,并且会把 3 --> T 的边变成废边(访问不到的边)。

然后从点 2 访问到点 3 的时候,遍历点 3 的出边的时候就没有 3 --> T 这条边了,又要等待下一次 dfs 才能增广。这算不算当前弧的负优化? 如图

2020/8/22 11:38
加载中...