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

P3376 【模板】网络最大流

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

从日报上看到：

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

但为什么 EK 能过而 Dinic TLE 了

（没错又是我）

by Zvelig1205 @ 2022-08-04 11:50:51

而且这篇日报的名字是《EK不够快？再学个Dinic吧》qwq

by wcyQwQ @ 2022-08-04 11:52:06

Dinic非常依赖当前弧优化，没有肯定T

by Zvelig1205 @ 2022-08-04 11:54:08

@wcywcywcywcy 那不加当前弧 Dinic 的时间复杂度上界是多少？

by AIskeleton @ 2022-08-04 11:55:46

@极冬寒雪 O(nm^2)

by wcyQwQ @ 2022-08-04 11:56:07

我也不是很清楚，学网络流不要太关注时间复杂度，一般跑不满，

by 方123456 @ 2022-08-04 12:03:53

我记得 dinic 不加当前弧也可以过的。

by 方123456 @ 2022-08-04 12:04:07

你是不是没加剪枝？

by 方123456 @ 2022-08-04 12:09:00

加了点小剪枝

by serene_analysis @ 2022-08-04 12:14:27

@极冬寒雪

minn=min(minn,val[i]);

第一条边是 0 后面就跑不动了。建议记录一个 \text{rest} 表示剩余可以流的流量，往后面 dfs 时流量传 \min(\text{rest},val_i)。

by Zvelig1205 @ 2022-08-04 17:16:07

@A_I_Skeleton 那为什么相同的复杂度上界，EK能A而Dinic不能？

| 下一页