众所周知,Dinic跑不满,并且我写的普通的Dinic最慢的点也只要128ms。你是不是使用了`memset`整个数组等等细节,让复杂度退化了?
by cosmicAC @ 2020-07-11 18:20:26
我知道原因了,请把Dinic的`Dfs`加上这么一行剪枝:
```cpp
if(d){
e[i].val -= d;e[i ^ 1].val += d;
res -= d;sum += d;
if(!res) break;
}
```
by cosmicAC @ 2020-07-11 18:29:58
@[cosmicAC](/user/30093) 太感谢您了!!!看样子以后写 Dinic 要注意了。
by Daniel_yuan @ 2020-07-11 18:38:06
@[Daniel_yuan](/user/71955) Orz
by No268435 @ 2020-07-11 18:58:45
@[Daniel_yuan](/user/71955) orz
by 弦巻こころ @ 2020-07-11 19:01:17
$log n$~~好香~~
by LuV_Studio @ 2020-07-11 19:16:19