Dinic TLE求助(悬赏关注)

P3376 【模板】网络最大流

YONIC @ 2022-05-21 08:33:07

建图时tot设0会WA#11,但是#9#10AC,设1会TLE#9#10,但#11AC

#include<bits/stdc++.h>
#define int long long
#define M 203
#define M2 (int)(5e3+3)
using namespace std;
int n,m,s,t,now,ans,dep[M<<1],l,r;
queue<int>Q;
bool vis[M];
class graph{
    public:
        int tot=1,head[M<<1];
        class edge{
            public:
                int nxt,to,w;
        };
        edge h[M2<<1];
        void add(int u,int v,int w){
            h[++tot].to=v;
            h[tot].nxt=head[u];
            h[tot].w=w;
            head[u]=tot;
        }
};
graph G;
bool BFS(){
    memset(dep,0,sizeof(dep));
    Q.push(s);
    dep[s]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=G.head[x];i;i=G.h[i].nxt){
            int y=G.h[i].to;
            if(G.h[i].w&&!dep[y]){ 
                dep[y]=dep[x]+1;
                Q.push(y);
            }
        }
    }
    return dep[t];
}
int DFS(int x,int in){
    if(x==t) return in;
    int out=in;
    for(int i=G.head[x];i&&out;i=G.h[i].nxt){
        int y=G.h[i].to;
        if(G.h[i].w&&dep[y]==dep[x]+1) {
            int res=DFS(y,min(G.h[i].w,out));
            G.h[i].w-=res;
            G.h[i^1].w+=res;
            out-=res;
            if(!out) break;
        }
    }
    if(!out) dep[x]=0;
    return in-out;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1,u,v,w;i<=m;++i){
        scanf("%lld%lld%lld",&u,&v,&w);
        G.add(u,v,w);
        G.add(v,u,0);
    }
    while(BFS()) ans+=DFS(s,1e18);
    printf("%lld\n",ans);
    return 0;
}

by LCATreap @ 2022-05-21 12:40:54

if(!out)dep[x]=0; 改成 if(out == in)dep[x]=0;

关我大号就行(


by LCATreap @ 2022-05-21 12:43:31

至于为什么 tot=0 会炸是因为反向边对应不上,tot=1 没问题。


|