蒟蒻刚学网络流，求问时间复杂度上界

P3376 【模板】网络最大流

Zvelig1205 @ 2022-08-04 11:49:06

从日报上看到：

对于这个题，显然 n,m 不同阶，所以 Dinic（没有当前弧优化，因为还没有学到）的时间复杂度应该是优于 EK 的

但为什么 EK 能过而 Dinic TLE 了

（没错又是我）

by AIskeleton @ 2022-08-04 17:30:36

@极冬寒雪可能因为 EK 的时间复杂度上界里只有一个 m 是紧的，一般情况下出题人不太会去卡，但 dinic 不加当前弧优化的时间复杂度无法保证，容易退化成 O(nm^2) 的复杂度，所以在模板题里就被卡了吧。

by Zvelig1205 @ 2022-08-04 17:59:58

@A_I_Skeleton 哦哦，谢谢dalao

上一页 |