为什么加了优化反而更慢求解惑

P4001 [ICPC-Beijing 2006] 狼抓兔子

并且加了优化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


|