并且加了优化TLE两个点(4.2s以上)
不加优化一个点200ms另一个点1.2s过了
by lzyzs @ 2023-08-09 08:54:30
Dinic 每次都要清空 cnt 数组。
by fjy666 @ 2023-08-09 09:41:46
@[fjy666](/user/366338) 不清空不会更快吗
by lzyzs @ 2023-08-10 08:05:34
@[lzyzs](/user/362762) +1
by LIUYC_C @ 2023-08-20 10:05:32
@[LIUYC_C](/user/819273) 所以为什么
by lzyzs @ 2023-08-20 10:28:31
你这是当前弧优化,$Dinic$ 算法加了复杂度才是 $O(n^2\times m)$,不加是 $O(n\times m^2)$。
当你高度重设后,路径也不在相同,注意一定要重设当前弧。
```cpp
while(bfs())
{
memset(now,0,sizeof(now));
ans+=dfs(s,MAXX);
cout << cntt << endl;
}
```
by sangshang @ 2023-12-23 21:24:34