求助dinic

P3376 【模板】网络最大流

ZhuMingYang @ 2020-07-11 20:56:39

数据突然duliu了

请问下面这两种有啥区别 为什么放前面就TLE?

ll dfs(int x,int in)
{
    if(x==t) return in;
    ll out=0;
    for(int &i=cur[x];i;i=edge[i].nxt)
    {
        int y=edge[i].to;
        if(dep[y]!=dep[x]+1||edge[i].val==0) continue;
        //if(!in) return out;放这就T
        int res=dfs(y,min(in,edge[i].val));
        edge[i].val-=res;
        edge[i^1].val+=res;
        in-=res;
        out+=res;
        if(!in) return out;//放这就过??
    }
    if(out==0) dep[x]=0;
    return out;
}

by ZhuMingYang @ 2020-07-11 21:01:24

想了一下 似乎是边还有残量 当前弧就正好记录到那条边?


by 辰星凌 @ 2020-07-11 21:02:23

自问自答可海星...


|