为什么 Dinic 这样写 DFS 这个题会 T
int DFS(int u,int flow)
{
if(u==t) return flow;
register int res=0;
for(register int &i=now[u];flow&&i;i=e[i].next)
if(e[i].w&&d[e[i].v]==d[u]+1)
{
register int t=DFS(e[i].v,min(flow,e[i].w));
if(!t) d[e[i].v]=INF;
e[i].w-=t,e[i^1].w+=t;
flow-=t,res+=t;
}
return res;
}
这样就过了,还跑得飞快
int DFS(int u,int flow)
{
if(u==t) return flow;
register int res=0;
for(register int &i=now[u];i;i=e[i].next)
if(e[i].w&&d[e[i].v]==d[u]+1)
{
register int t=DFS(e[i].v,min(flow,e[i].w));
if(!t) d[e[i].v]=INF;
e[i].w-=t,e[i^1].w+=t;
flow-=t,res+=t;
if(!flow) break;
}
return res;
}
之前的题都没有出锅
我寻思这两种写法不是等价的吗