关于dinic的bfs实现细节讨论

P3376 【模板】网络最大流

zty02281128 @ 2024-12-11 11:24:48

rt

请问这两种return方式有时间复杂度的区别吗？

if(v==t) return 1;
//遇到了汇点就return 900ms
return dep[t]!=INF;
//bfs结束后判断 930ms

by ATZdhjeb @ 2024-12-11 11:30:44

不是哥们？

by ATZdhjeb @ 2024-12-11 11:32:27

其实是没有的，但是第一种确实常数小一点

by __Louis__ @ 2024-12-11 11:37:12

当然有的，因为遇到汇点既可以直接推出的，类似于剪枝。

by ATZdhjeb @ 2024-12-11 11:37:50

@Louis 为啥有复杂度上的差别来着？

by NATO @ 2024-12-11 11:43:39

@Louis NMP 我每增广一次增广路长度都会 +1，最坏找 n 次，在给图分层的时候不是只有 \ge 当前 t 的深度的点被减掉复杂度优化了尼玛吗？

by __Louis__ @ 2024-12-11 13:11:03

复杂度啊，看错了，没有，只是剪枝，对复杂度没有影响 qwq。

@ATZdhjeb

@NATO

|