关于Dinic的疑问

P3376 【模板】网络最大流

_cheng @ 2024-07-26 16:05:59

请问

这是bfs

bool bfs(int st){
    while(q.size())  q.pop();
    for(int i=1; i<=n; ++i)  dep[i] = -1; 
    for(int i=1; i<=n; ++i)  cur[i] = head[i] ;

    q.push(st);  dep[st] = 0;
    while(q.size()){
        int p = q.front(); q.pop();
        for(int i=head[p]; i; i=e[i].nxt){
            if(dep[e[i].to]!=-1 || e[i].w<=0)  continue ;      //遍历过了, 排掉, 因为要取最短   //边权为0, 排掉, 因为加入后无法增广(瓶颈为0)
            dep[e[i].to] = dep[p] + 1;
            q.push(e[i].to);
            if(e[i].to == en)   return 1;      //这个时候说明所有<dis[en]的都遍历完了(因为是bfs), 所以就return 1
        }
    }
    return 0;      //无论怎么扩大都无法抵达end, 说明管子几乎都装满了, 没有可以增广的路了
}

这是dfs

ll dfs(int x, ll last){       //last: 剩余流量
    if(x == en)   return last ;     //终点的一定可以流出去, 所以剩多少, 留多少

    ll mxflow_sum = 0ll;       //从这个点出去的最大流们之和
    for(int i=cur[x]; i && last; i=e[i].nxt){     //小优化: 剩余0了, 反正流不了, 直接退
        cur[x] = i ;      //"当前弧"优化: 流满的路径(即e[i-1]), 下次来时不用再遍历, 反正下面的mxflow已经确定了, 已经流满了, 你再来, 也流不进去, 所以就从没流过或流了一半的开始(e[i]及以后)
        int v = e[i]. to;
        if(dep[v]!=dep[x]+1 || e[i].w<=0)   continue ;         //不满足层序以及瓶颈为0的都要排掉

        ll mxflow = dfs(v, min(e[i].w, last));     //从这个节点到end的最大流
        if(mxflow == 0)  {dep[v] = -1; continue;}  //从这个节点到结尾的增广路最大流为0, 下次要么一样, 要么更小, 所以不可能再对答案有贡献了, 直接堵掉
        e[i].w -= mxflow , e[i^1].w += mxflow ;   //这一条边也在路径上, 也要减掉mxflow
        last -= mxflow, mxflow_sum += mxflow ;    //剩余的流(last)要减去这条管子路径的流
    }
    return mxflow_sum;
}

为什么dfs里, 遍历到一个新点, 也要判断边权是否为0? (if(dep[v]!=dep[x]+1 || e[i].w<=0) continue ;)边权为0的, 之前bfs不是排掉了吗?

等待dalao的出现awa


by Obijeb @ 2024-07-26 16:17:57

@_cheng 在dfs推流的过程中,可能重复经过一些点,也会有重复的边

一条边可能在上一次经过该点的时候被流干了


by _cheng @ 2024-07-26 16:32:11

O, 对耶, e[i].w会重新赋值, 流完了就是0了


by _cheng @ 2024-07-26 16:32:38

感谢


|