关于最大流时间复杂度
  • 板块灌水区
  • 楼主FiresonZ
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/13 21:42
  • 上次更新2023/10/27 20:31:23
查看原帖
关于最大流时间复杂度
639483
FiresonZ楼主2022/7/13 21:42

这道题它题解里面说EK不能过,会卡EK,但是为啥我使用了一个据说是比EK弱的Dfs实现FF最大流可以过啊?

这个dfs长这个样子

gg dfs(const gg &p,const gg &x)
{
    if(p==t||x==0) return x;
    alr[p]=true;
    for(gg i=head[p];i;i=nxt[i])
    {
        if(alr[to[i]]) continue;
        gg t=dfs(to[i],min(x,cap[i]-flow[i]));
        if(t)
        {
            flow[i]+=t;
            flow[i^1]-=t;
            return t;
        }
    }
    return 0;
}
2022/7/13 21:42
加载中...