thomaswmy @ 2023-09-14 16:39:13
今天在写上下界最小流的时候，用 dinic 怎么写都会 T 一两个点，卡常未果。然后发现建完图直接跑最大流也会 T 。
参考了别人的提交记录，把原来 dinic 的 dfs 从这样
ll rest = flow;
for (int &i = now[u]; i && rest; i = edge[i].nxt) {
int v = edge[i].to;
ll w = edge[i].w;
if (d[v] != d[u] + 1 || !w) continue;
ll k = dinic(v, min(rest, w));
if (!k) d[v] = 0;
edge[i].w -= k, edge[i ^ 1].w += k;
rest -= k;
}在 for 循环最后加了一句
if (!rest) return flow;后就跑的飞快，可以看到第 8 个点从 1050+ms 到了 15ms ，将近 100 倍。
发现其主要问题在于写当前弧的时候 i 是引用，把 i 取消引用后效果一样。
所以说，为啥引用会这么慢？？？
最终对比：
引用的 dinic 86分，非引用100分，快了非常多
怕发到 LOJ 没人看就发到这了
by thomaswmy @ 2023-09-14 16:40:30
感觉一般网络流数据范围都不大，对比不出来。这道题就很明显
by reveal @ 2023-09-14 16:42:57
@thomaswmy 你不及时 return 还加当前弧优化退化成 EK 了
by optimize_2 @ 2023-09-14 16:43:12
3。
by thomaswmy @ 2023-09-14 16:44:03
@reveal 能不能仔细看代码，for 里条件有 rest
by reveal @ 2023-09-14 16:45:01
首先就是当前弧优化的跳出条件, 我为啥要把"除了最后一条边之外"那句话加粗呢? 因为你如果把跳出判定写在for循环里会慢
10 倍以上, 根本不是常数问题, 是复杂度出了锅. 因为你会漏掉最后那个可能没跑满的弧, 而分层图BFS会在当前图没有被割断的时候一直跑跑跑, 于是就锅了.——rvalue
by thomaswmy @ 2023-09-14 16:48:40
@reveal 哦我悟了，对不起
by thomaswmy @ 2023-09-14 16:53:33
验证了一下，确实是这样
by thomaswmy @ 2023-09-14 16:56:13
可以看到，确实不是引用常数的问题
by FerventTemp0 @ 2023-09-14 17:22:49
@reveal 博客写的太优质了。支持一波
by reveal @ 2023-09-14 17:29:06
@FerventTempo 不是我写的 at 我干嘛