关于在费用流中这个(伪)Dinic的时间复杂度
查看原帖
关于在费用流中这个(伪)Dinic的时间复杂度
605333
Obijeb楼主2024/7/22 20:18

如题,感觉在最短路唯一的情况下其实就是单路增广,还访问了很多无效节点

看起来好像还不如EK

求教时间复杂度

int dfs(int p,int fl)
{
    if(p==t)
        return fl;
    if(fl==0 || vis[p])
        return 0;
    vis[p]=1;
    int sfl=0;
    for(int i=nhead[p];i && fl;i=e[i].next)
    {
        nhead[p]=i;
        if(dis[e[i].v]==dis[p]+e[i].w && e[i].fl)
        {
            int dfl=dfs(e[i].v,min(fl,e[i].fl));
            mxcst+=dfl*e[i].w;
            sfl+=dfl;
            fl-=dfl;
            cg(i,dfl);
        }
    }
    vis[p]=0;
    return sfl;
}

为节约版面只放推流部分

2024/7/22 20:18
加载中...