先放上两段代码,区别只有一行,已经标出:
LL Dinic(CI &x,LL flow)
{
if(x==t or !flow) Heriko flow;
int i;
LL k,y,rst=flow;
for(i=now[x];i and rst;i=r[i].nex)
{
y=r[i].to;
if(dis[y]==dis[x]+1 and r[i].val)
{
k=Dinic(y,Hmin(rst,r[i].val));
if(!k) {dis[y]=0;continue;}
r[i].val-=k;
r[i^1].val+=k;
rst-=k;
}
}
now[x]=i;
Heriko flow-rst;
}
LL Dinic(CI &x,LL flow)
{
if(x==t or !flow) Heriko flow;
int i;
LL k,y,rst=flow;
for(i=now[x];i and rst;i=r[i].nex)
{
y=r[i].to;
if(dis[y]==dis[x]+1 and r[i].val)
{
k=Dinic(y,Hmin(rst,r[i].val));
if(!k) {dis[y]=0;continue;}
r[i].val-=k;
r[i^1].val+=k;
rst-=k;
}
if(!rst) break;//这里
}
now[x]=i;
Heriko flow-rst;
}
前者 TLE 两个点,后者 AC 了。
问题就是多出来的那句为什么会变快?