而且这篇日报的名字是《EK不够快?再学个Dinic吧》qwq
by Zvelig1205 @ 2022-08-04 11:50:51
Dinic非常依赖当前弧优化,没有肯定T
by wcyQwQ @ 2022-08-04 11:52:06
@[wcywcywcywcy](/user/587248) 那不加当前弧 Dinic 的时间复杂度上界是多少?
by Zvelig1205 @ 2022-08-04 11:54:08
@[极冬寒雪](/user/413020) $O(nm^2)$
by AIskeleton @ 2022-08-04 11:55:46
我也不是很清楚,学网络流不要太关注时间复杂度,一般跑不满,
by wcyQwQ @ 2022-08-04 11:56:07
我记得 dinic 不加当前弧也可以过的。
by 方123456 @ 2022-08-04 12:03:53
你是不是没加剪枝?
by 方123456 @ 2022-08-04 12:04:07
[加了点小剪枝](https://www.luogu.com.cn/paste/ah9zznfc)
by 方123456 @ 2022-08-04 12:09:00
@[极冬寒雪](/user/413020)
```
minn=min(minn,val[i]);
```
第一条边是 $0$ 后面就跑不动了。建议记录一个 $\text{rest}$ 表示剩余可以流的流量,往后面 dfs 时流量传 $\min(\text{rest},val_i)$。
by serene_analysis @ 2022-08-04 12:14:27
@[A_I_Skeleton](/user/540715) 那为什么相同的复杂度上界,EK能A而Dinic不能?
by Zvelig1205 @ 2022-08-04 17:16:07