请问dinic为什么这样优化就快得飞起

P3376 【模板】网络最大流

因为这个break是内层循环里面的,而总所周知网络流一个点要连一堆边。你加了这个可能只需要跑几条边就退出,你不加就每次都得跑几十条边。
by 0htoAi @ 2021-07-31 16:06:07


其实真正的原因应该是你加了当前负优化,如果$flow=0$ 时不 `break` 掉后面的边这次增广都走不了了,于是增广次数大大增加,~~慢的堪比 FF~~。
by 约瑟夫用脑玩 @ 2021-07-31 16:11:12


@[Yahbim](/user/372708)
by 约瑟夫用脑玩 @ 2021-07-31 16:11:29


@[约瑟夫用脑玩](/user/158948) 懂了,谢谢!
by Yahbim @ 2021-07-31 16:42:22


@[hanhan_zz](/user/335366) 知道了,谢谢qwq
by Yahbim @ 2021-07-31 16:42:54


@[Yahbim](/user/372708) 原因是您太巨了(手动滑稽
by Ckger @ 2021-07-31 21:24:48


@[Ckger](/user/215590) 捕捉
by Yahbim @ 2021-07-31 22:04:13


@[Yahbim](/user/372708) 恭喜您捕捉到一枚蒟蒻
by Ckger @ 2021-07-31 23:08:16


|