关于dinic

灌水区

ningago @ 2022-03-19 13:42:31

看到很多大佬都这么写dfs

//cur[i] :当前弧优化

//k,c :当前节点与当前流量

//ceng[i] :层数

//w[i]i 容量

ll dfs(ll k,ll c)
{
    ll res = 0;
    if(k == T)
        return c;
    for(ll i = cur[k];~i && c;i = ne[i])
    {
        cur[k] = i;
        ll nx = e[i];
        if(ceng[nx] == ceng[k] + 1 && w[i])
        {
            ll t = dfs(nx,min(w[i],c));
            if(!t)
                ceng[nx] = -1;
            w[i] -= t;
            w[i ^ 1] += t;
            res += t;
            c -= t;
        }
    }
    return 0;
}

而蒟蒻我是这么写的:

ll dfs(ll k,ll c)
{
    if(k == T)
        return c;
    for(ll i = cur[k];~i;i = ne[i])
    {
        cur[k] = i;
        ll nx = e[i];
        if(ceng[nx] == ceng[k] + 1 && w[i])
        {
            ll t = dfs(nx,min(w[i],c));
            if(t > 0)
            {
                w[i] -= t;
                w[i ^ 1] += t;
                return t;
            }
        }
    }
    return 0;
}

我这个写法是不是有什么问题或确点啊 qwq


by yzh_Error404 @ 2022-03-19 13:45:25

没有炸边,下一次还会走这条边?


by ningago @ 2022-03-19 13:46:43

@yzh_Error404

有当前弧不会再走了吧?


by Foreverxxx @ 2022-03-19 13:51:42

流出量为 0 时应该把这条边给炸掉,不然会重复走,这是 Dinic 算法的一个很好的优化


by ningago @ 2022-03-19 13:54:51

@Foreverxxx

%%% 那后面的写法在 if(t>0) 前面加上 if(!t) ceng[nx] = -1;会和上面一样吗?


by Foreverxxx @ 2022-03-19 14:04:27

@ningago 对的,如果流不出去,直接设置层数使得不会再次遍历到这条边就行了。


by ningago @ 2022-03-19 14:09:05

@Foreverxxx 蟹蟹


|