哇，为什么我的dinic的当前弧优化没有用啊

Sarah @ 2018-03-26 16:04:34

by Loner_Knowledge @ 2018-03-26 17:31:34

BFS完后应该把cur置为每一个点的第一条边吧，是不是少了？

by Loner_Knowledge @ 2018-03-26 17:36:34

@Sarah

by Sarah @ 2018-03-27 11:31:03

没少啊。。。QAQ

by Loner_Knowledge @ 2018-03-27 15:27:49

@Sarah

我指的是每次BFS后都要把cur置为每一个点的第一条边，例如我的代码里就是这样：

int Dinic() {
    int ans=0;
    while(BFS()) {
        memcpy(Cur+1,First+1,n*sizeof(int));
        ans+=DFS(s,Inf);
    }
    return ans;
}

by Sarah @ 2018-03-27 18:59:33

@Loner_Knowledge 我bfs完了之后都把cur清空成0，然后在需要用到的时候判断一下cur是不是0，如果是0的话就把cur赋值为第一条边的位置，理论上是一样的啊QAQ

bool bfs(int s,int t){
    memset(dist,127,sizeof(dist));
    dist[s]=0;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        int x=pos[u];
        while(x){
            if((dist[edges[x].to]>(dist[u]+1))&&(edges[x].cap-edges[x].flow>0)){
                dist[edges[x].to]=dist[u]+1;
                q.push(edges[x].to);
            }
            x=edges[x].next;
        }
    }
    return dist[t]<2100000000;
}
int cur[100005];
int dinic(int v,int a){
    if((v==t)||(a==0)){
        return a;
    }
    int flow=0,f;
    if(!cur[v]) cur[v]=pos[v];
    int &x=cur[v];
    while(x){
        if((dist[v]+1)==dist[edges[x].to]){
            int minf=min(edges[x].cap-edges[x].flow,a);
            f=dinic(edges[x].to,minf);
            flow+=f;
            edges[x].flow+=f;
            edges[(x+1)^1-1].flow-=f;
            a-=f;
            if(a==0) break;
        }
        x=edges[x].next;
    }
    return flow;
}