为什么当前弧优化这样会很慢?

P3376 【模板】网络最大流

@[cqbzzqw](/user/383782) 因为当前边并不一定是断开的,可能推过来的流用完了导致退出了,但是此时当前边仍可以推流。 考虑后面为什么要写 `if (!u) return all;` 就是为了不会错误的跳边,不然这一句为什么不写循环条件里。
by reveal @ 2023-05-03 20:30:47


@[cqbzzqw](/user/383782) 你这条边这次也不一定流满,那你这一轮不再访问它就会导致轮数增加
by DitaMirika @ 2023-05-03 20:33:12


对的,我也是这样的,十分疑惑。
by TulipeNoire @ 2023-05-03 20:36:55


@[cqbzzqw](/user/383782) 1~n-2 与 n-1 连边,流量1,n-1与n连边流量n-2,这样你每 dfs 到 n-1 一次,只用了一个流量,就会退回去(cur 超过了 size),然后搞一遍分层。 你说挂不挂。
by Others @ 2023-05-03 20:44:40


哦,还得有个 0 给 1~n-2 流量。
by Others @ 2023-05-03 20:45:33


@[DitaMirika](/user/236862) @[reveal](/user/523491) @[Others](/user/383791) 悟了,谢谢大佬们
by StarPatrick @ 2023-05-03 21:00:42


|