为什么我的dinic还没有EK快？

Lzy21759 @ 2021-11-10 10:36:48

by Natsume_Rin @ 2021-11-10 10:40:39

看不见。但是我有理由怀疑你 dinic 没有用当前弧优化。

by Natsume_Rin @ 2021-11-10 10:42:12

好像是因为我没开代码公开。。。

by zhiyangfan @ 2021-11-10 10:42:28

@Lzy21759 不加当前弧优化和必要剪枝的 Dinic 复杂度无法保证。

by Echidna @ 2021-11-10 11:22:19

@Lzy21759

int dinic(int p,int flow)
{
    if(p==t)return flow;
    int rest=flow,k;
    for(int i=hed[p];i;i=nxt[i])
    {
        int tp=ver[i];
        if(d[tp]==d[p]+1&&edg[i])
        {
            k=dinic(tp,min(rest,edg[i]));
            if(!k)d[tp]=0;
            edg[i]-=k;
            edg[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

你这 i 没加引用。当前弧加了，但没加上

by Echidna @ 2021-11-10 11:23:22

好，我说错了，你这根本没加当前弧优化

by Lzy21759 @ 2021-11-10 11:56:56

马上去加。谢谢神犇们。

by qwq自动机 @ 2021-11-10 20:28:01

Cu Ball qwq

Dinic 347ms

EK 236ms

by OIerAlbedo @ 2021-11-16 22:20:08

我的dinic还没有FF快

by peterwuyihong @ 2021-11-17 19:48:46

@黄旭泽