刚学网络流,60Pts RE 求助

P3376 【模板】网络最大流

LordLeft @ 2019-12-17 18:59:10

RT,这个代码可以过预留推进的板子,但是过不了这个题,就很诡异

求dalao帮忙看一下

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
using namespace std;
int read(){
    int w=0;
    bool s=0;
    char c=getchar();
    while(!isdigit(c)){
        s=(c=='-');
        c=getchar();
    }
    while(isdigit(c)){
        w=w*10+c-'0';
        c=getchar();
    }
    return s?-w:w;
}   
const int N=200005,M=3000005,inf=2147483647;
int n,m,S,T,ans;
struct Graph{
    #define Ed Graph::Edge
    struct Edge{
        int to,flow;
        Edge *nxt,*ops;
    };
    Edge e[M<<1],*head[N];
    int cnt;
    void add_for(int u,int v,int w){
        e[++cnt]=(Edge){v,w,head[u],((cnt&1)?&e[cnt+1]:&e[cnt-1])};
        head[u]=&e[cnt];
    }
    void add(int u,int v,int w){
        add_for(u,v,w);
        add_for(v,u,0);
    }
    void reset(int s){
        for(int i=1;i<=s;i++){
            head[i]=NULL;
        }
        cnt=0;
    }
};
Graph G;
int h[N],gap[N<<1],sto[N];
bool vis[N];
struct cmp{
    bool operator ()(int a,int b)const{
        return h[a]<h[b];
    }
};
priority_queue<int,vector<int>,cmp>p_que;
queue<int>que;
bool BFS(){
    for(int i=1;i<=n;i++){
        h[i]=inf;
    }
    h[T]=0;
    que.push(T);
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(Ed *i=G.head[u];i!=NULL;i=i->nxt){
            int v=i->to;
            if((i->ops)->flow&&h[v]>h[u]+1){
                h[v]=h[u]+1;
                que.push(v);
            }
        }
    }
    return h[S]!=inf;
}
void push(int u){
    for(Ed *i=G.head[u];i!=NULL&&sto[u];i=i->nxt){
        int v=i->to;
        if(i->flow&&h[v]+1==h[u]){
            int flow=min(sto[u],i->flow);
            i->flow-=flow;
            (i->ops)->flow+=flow;
            sto[u]-=flow;
            sto[v]+=flow;
            if(v!=S&&v!=T&&!vis[v]){
                p_que.push(v);
                vis[v]=1;
            }
        }
    }
}
void relabel(int u){
    h[u]=inf;
    for(Ed *i=G.head[u];i!=NULL;i=i->nxt){
        int v=i->to;
        if(i->flow&&(h[v]+1<h[u])){
            h[u]=h[v]+1;
        }
    }
}
int HLPP(){
    if(!BFS()){
        return 0;
    }
    h[S]=n;
    for(int i=1;i<=n;i++){
        if(h[i]!=inf){
            gap[h[i]]++;
        }
    }
    for(Ed *i=G.head[S];i!=NULL;i=i->nxt){
        int v=i->to;
        if(i->flow){
            int flow=i->flow;
            i->flow-=flow;
            (i->ops)->flow+=flow;
            sto[S]-=flow;
            sto[v]+=flow;
            if(v!=S&&v!=T&&!vis[v]){
                p_que.push(v);
                vis[v]=1;
            }
        }
    }
    while(!p_que.empty()){
        int u=p_que.top();
        p_que.pop();
        vis[u]=0;
        push(u);
        if(sto[u]){
            gap[h[u]]--;
            if(!gap[h[u]]){
                for(int v=1;v<=n;v++){
                     if(v!=S&&v!=T&&h[v]>h[u]&&h[v]<n+1){
                        h[v]=n+1;
                     }
                }
            }
            relabel(u);
            gap[h[u]]++;
            p_que.push(u);
            vis[u]=1;
        }
    }
    return sto[T];
}
int main(){
    n=read(),m=read(),S=read(),T=read();
    G.reset(n);
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read(),v=read(),w=read();
        G.add(u,v,w);
    }
    ans=HLPP();
    printf("%d\n",ans);
    return 0;
}

by 辰星凌 @ 2019-12-17 19:01:26

ORZ网络瘤巨佬


by ACAね @ 2019-12-17 19:30:43

@LordLeft Orz


by qian_shang @ 2019-12-17 19:40:22

@LordLeft 网络流?我来我来,指针?算了算了


|