当前弧优化是啥啊,是 dfs 中的那个引用吗。据说 LOJ 的网络流板子卡不加当前弧优化的 Dinic,但是我把引用去掉也过了啊(比加上引用慢了一点,但还是跑得飞快)
传说中的引用:
#define int long long
int dfs(int u=S,int mx=1e18){
if(u==T) return mx;
int lst=mx;
for(int&i=hd[u];i;i=nxt[i]){//就是这里
int v=to[i];
if(dep[v]!=dep[u]+1ll||!now[i]) continue;
int t=dfs(v,min(lst,now[i]));
if(!t) dep[v]=0ll;
else { now[i]-=t; now[i^1ll]+=t; lst-=t; }
if(!lst) break;
}
return mx-lst;
}
完整代码(加引用)
完整代码(不加引用)