之前写 dinic 时都是这么写 dfs 的:
inline ll dfs(ll u,ll fl){
if(u==t)return fl;
ll re=fl,i;
for(i=cur[u];i&&re;i=nx[i]){
if(d[to[i]]==d[u]+1&&w[i]){
ll k=dfs(to[i],min(re,w[i]));
if(!k)d[to[i]]=0;
re-=k; w[i]-=k; w[i^1]+=k;
}
}
cur[u]=i;
return fl-re;
}
然后因为学校造了加强的数据做题的时候莫名一直在T,卡常的过程中偶然改成了这样:
inline ll dfs(ll u,ll fl){
if(u==t)return fl;
ll re=fl;
//把i的定义放进循环了(其他都一样
for(rint i=cur[u];i&&re;i=nx[i]){
if(d[to[i]]==d[u]+1&&w[i]){
ll k=dfs(to[i],min(re,w[i]));
if(!k)d[to[i]]=0;
re-=k; w[i]-=k; w[i^1]+=k;
}
cur[u]=i;
}
return fl-re;
}
然后: 7s→0.5s,窝整个人都傻了
本来以为可能是 i 定义在循环里就会快,然后又这样写了一下:
inline ll dfs(ll u,ll fl){
if(u==t)return fl;
ll re=fl;
for(rint i=cur[u];i&&re;i=nx[i],cur[u]=i){ //把当前弧优化放进for了
if(d[to[i]]==d[u]+1&&w[i]){
ll k=dfs(to[i],min(re,w[i]));
if(!k)d[to[i]]=0;
re-=k; w[i]-=k; w[i^1]+=k;
}
}
return fl-re;
}
却发现跟原来差不多甚至慢了一点
有dalao知道这是怎么回事吗qaq蒟蒻不胜感激