对当前弧优化的疑惑

P3376 【模板】网络最大流

Calanosay @ 2021-04-20 19:54:27

bool bfs(){
    queue<int> q;
    q.push(s);
    memset(dis,-1,(n+1)*sizeof(int));
    dis[s]=0;
    noww[s]=head[s];
    while(!q.empty()){
        int node=q.front();q.pop();
        for(int i=head[node];i!=-1;i=nex[i]){
            int to=v[i];
            if(dis[to]==-1&&w[i]){
                dis[to]=dis[node]+1;
                q.push(to);
                noww[to]=head[to];
            }
        }
    }
    return dis[t]!=-1;
}
ll dfs(int x,ll flo){
    if(x==t)    return flo;
    ll now=flo;
    for(int i=noww[x];i!=-1;i=nex[i]){
        noww[x]=i;
        int to=v[i];
        if(dis[to]==(dis[x]+1)&&w[i]){
            ll d=dfs(to,min(now,w[i]));
            now-=d;
            w[i]-=d,w[i^1]+=d;
            if(!now)    break;
        }
    }
    return flo-now;
}

每次dfs通一条路之后now数组都会重置,但是在你dfs的时候不是只会一直往下面搜索吗,我理解now数组的作用是在你遍历到now[x],x这个结点的时候起到一个传送作用,但是既然你是一直往后搜索,等于你dfs之后无法再次遍历到x这个结点了,也就是无法传送了。。所以我哪里理解有错误,这个优化明明很好,但我不理解


by wheneveright @ 2021-04-20 20:01:45

因为你这次经过了这条边,如果这条边是属于一个增广路的,那么它被选择了一定可以把它的能力全部发挥,而如果这一次都经过它,但是没有增广路那么下一次更不可能会用到它


by Calanosay @ 2021-04-20 20:06:25

@wheneveright 这我是明白的,我只是有些疑惑它的原理。。。这个优化是不是在稠密图作用明显呢?我觉得这个操作在一条路可以直接走到通,没有分叉的情况下是没有作用的。


by wheneveright @ 2021-04-20 20:08:00

@Fucker_Chao 它防的就是这种情况


by Calanosay @ 2021-04-20 20:09:09

@wheneveright 好的谢谢.


by wheneveright @ 2021-04-20 20:09:15

@Fucker_Chao 在稀疏途中加不加优化都无所谓,但是在部分稠密图可以把复杂度优化到 \operatorname{O}(n+e)


by hly1204 @ 2021-04-20 20:15:59

无重边的话好像确实不用考虑


by hly1204 @ 2021-04-20 20:22:37

因为你是多路,所以无重边确实无所谓的,只要保证一次是 O(nm) 就行了。。


|