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 FerventTemp0 @ 2023-09-14 17:46:32
哦这样，看错id了。
by yinhee @ 2023-09-17 09:28:42
@reveal 所以究其原因是e[i].nxt略过了一条边是吗？
by reveal @ 2023-09-18 21:19:43
@yinhee 是的，最后一条没跑完的边被跳掉了才退出
by yinhee @ 2023-09-18 21:57:11
@reveal 好的，谢谢
by Aresword_2 @ 2023-09-20 19:32:44
@thomaswmy 关于这个问题，请看下面一段代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll i=0;
for(i=1;i<=3;i++);
cout<<i<<endl;
//输出4
return 0;
}这个代码的输出为 4 ，所以你可以知道，你把 rest 写在 for 循环里，会导致即使你判断了 rest 跳出，你的 now[u] 也跳到下一条边去了。
这样你最后一条边其实没有跑满，下一次也忽略了这条边，就出现了 reveal 提到的问题。
而你使用非引用的方式修改的话，now[u]=i 是在 for 循环里的，因此不会执行，就不会忽略了最后一条边。