你的当前弧呢(
by Register_int @ 2022-11-30 18:42:17
加上当前弧优化
by _slb @ 2022-11-30 19:19:06
@[Register_int](/user/406941) @[_slb](/user/373429)
其实是有当前弧优化的:
```c++
for (register int i = now[u];i && lost;i = e[i].nxt, now[u] = i)
```
---
@[kirihara233](/user/701221)
这里引用 rvalue 在 [[教程]网络流详解: 从入门到放弃](https://blog.rvalue.moe/10650849/) 中的两句话:
> 然后最关键的决定时间复杂度的优化是当前弧优化, 我们每次向某条边的方向推流的时候, 肯定要么把推送量用完了, 要么是把这个方向的容量榨干了. **除了最后一条因为推送量用完而无法继续增广的边**之外其他的边一定无法继续传递流量给 $t$ 了
> 为啥我要把一个 Dinic 讲得这么细呢? 况且它确实真的只是个建模之后跑一下的工具?
>
> 因为如果你不理解 Dinic 的过程与复杂度分析, 你几乎**一 定 会 写 假**.
>
> 有些看起来很不起眼的小细节可能影响着整个算法的时间复杂度.
>
> 首先就是当前弧优化的跳出条件, 我为啥要把"除了最后一条边之外"那句话加粗呢? 因为你如果把跳出判定写在 `for` 循环里会慢 $10$ 倍以上, 根本不是常数问题, 是复杂度出了锅. 因为你会漏掉最后那个可能没跑满的弧, 而分层图 BFS 会在当前图没有被割断的时候一直跑跑跑, 于是就锅了.
你需要在 `lost` 以及流量计算完毕之后立刻判断 `lost` 是否为 $0$ 并跳出,而不是在 `for` 中判断。
另外这都什么年代了还在用 `register` 卡常。
by reveal @ 2022-11-30 19:28:03
@[reveal](/user/523491) 对不起眼瞎了(
by Register_int @ 2022-11-30 19:29:00
@[reveal](/user/523491) 谢谢大佬!(完了,现在用 `register` 用惯了,改不过来了
by char_cha_ch @ 2022-11-30 22:05:27
@[reveal](/user/523491) 它那个lost没有问题吧,实现方式完全不一样啊,原文里用的指针,那个当前弧优化的更新是在for循环里的,而楼主写的当前弧优化是在下面的,也就是说for里面的那个判断是并没有更新当前弧优化
by 聊机 @ 2023-01-07 20:48:15
@[reveal](/user/523491) 这改不改都一样的
by 聊机 @ 2023-01-07 20:48:45
@[kirihara233](/user/701221) 我觉得你变慢的原因就是所谓卡常加的register,register不能乱加吧,register只应该用于不需要保存的中间量,而且O2会自动帮你开一些(或者只是评测机波动),你这“不卡常”都加快读,你所谓的卡不卡有什么区别呢?
by 聊机 @ 2023-01-07 21:22:54
@[聊机](/user/290959) 额,现在这个帖子已经没什么意义了吧,问题都解决了。
by char_cha_ch @ 2023-01-07 21:29:11