关于dinic
  • 板块灌水区
  • 楼主ningago寄寄人
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/3/19 13:42
  • 上次更新2023/10/28 06:13:41
查看原帖
关于dinic
371968
ningago寄寄人楼主2022/3/19 13:42

看到很多大佬都这么写dfs

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

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

//ceng[i]ceng[i] :层数

//w[i]w[i]ii 容量

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;
}

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

2022/3/19 13:42
加载中...