代码:
ll dfs(int u,ll flow){
if(u==t || !flow) return flow;
ll res=0;
for(int &i=headc[u];i;i=edge[i].nxt){
int v=edge[i].to;ll &w=edge[i].w,&fw=edge[i^1].w;
if(w && depth[v]==depth[u]+1){
ll delta=dfs(v,min(w,flow));
if(!delta) continue;
w-=delta,fw+=delta;
res+=delta,flow-=delta;
if(flow==0) break;
}
}
if(res==0) depth[u]=-1;
return res;
}
其中
if(flow==0) break;
这一句,如果加了,就是57ms;如果没加,就是1.05s,差距相当大。但是,我在开头处有
if(u==t || !flow) return flow;
这一句,同样保证了流量为0的无贡献点不会搜下去。它们俩唯一的差别只在于几次int和几次加减法的有无,然而它们的时间开销真的有这么大么?