蒟蒻100分求助，为啥我的当前弧优化dinic这么慢

yangshiyu10 @ 2022-08-11 09:00:56

by yangshiyu10 @ 2022-08-11 09:01:05

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define ll long long
using namespace std;
ll re(){
    ll x=0;int f=1;char t=getchar();
    while(t<'0'||t>'9'){if(t=='-')f=-1;t=getchar();}
    while(t>='0'&&t<='9')x=x*10+t-'0',t=getchar();
    return x*f;
}
const int N=210,M=10010;
int n,m,s,t;
int fir[N],poi[M],net[M],sumb=1;
ll val[M];
void add(int a,int b,int c){
    net[++sumb]=fir[a];
    poi[sumb]=b;
    val[sumb]=c;
    fir[a]=sumb;
}
int vis[N];
ll ans=0;
int l[N],head,tail;
int la_e[N],dep[N];
int bfs(){
    for(int i=1;i<=n;i++){
        vis[i]=0;
        la_e[i]=fir[i];
        dep[i]=1e9;
    }
    int pdt=0;
    dep[s]=0;
    head=0,tail=1;
    l[1]=s;
    while(head<tail){
        int now=l[++head];
        vis[now]=0;
        for(int i=fir[now];i;i=net[i]){
            int p=poi[i];
            if(dep[p]==1e9&&val[i]){
                dep[p]=dep[now]+1;
                if(p==t){
                    return 1;
                }
//              {pdt=1;continue;}
                if(vis[p])continue;
                l[++tail]=p;
                vis[p]=1;
            }
        }
    }
    return pdt;
}
ll dfs(int x,ll flow){
    if(x==t){
        ans+=flow;
        return flow;
    }
    ll used=0;
    for(int i=la_e[x];i&&flow;i=net[i]){
        la_e[x]=i;//当前弧优化 
        int p=poi[i];
        if(dep[p]==dep[x]+1&&val[i]){
            ll nf=0;
            if(nf=dfs(p,min(flow-used,val[i]))){
                val[i]-=nf;
                val[i^1]+=nf;
                used+=nf;
                if(used==nf)return used;
            }
        }
    }
    return used;
}
void dinic(){
    while(bfs()){
        dfs(s,1e9);
    }
    return;
}
int main(){
    n=re(),m=re(),s=re(),t=re();
    for(int i=1;i<=m;i++){
        int x1=re(),x2=re(),x3=re();
        add(x1,x2,x3);
        add(x2,x1,0);
    }
    dinic();
    printf("%lld\n",ans);
    return 0;
}

by 方123456 @ 2022-08-11 09:04:43

要加点其他的剪枝

by 方123456 @ 2022-08-11 09:10:09

加了点小剪枝，压下去了！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define ll long long
using namespace std;
ll re(){
    ll x=0;int f=1;char t=getchar();
    while(t<'0'||t>'9'){if(t=='-')f=-1;t=getchar();}
    while(t>='0'&&t<='9')x=x*10+t-'0',t=getchar();
    return x*f;
}
const int N=210,M=10010;
int n,m,s,t;
int fir[N],poi[M],net[M],sumb=1;
ll val[M];
void add(int a,int b,int c){
    net[++sumb]=fir[a];
    poi[sumb]=b;
    val[sumb]=c;
    fir[a]=sumb;
}
int vis[N];
ll ans=0;
int l[N],head,tail;
int la_e[N],dep[N];
int bfs(){
    for(int i=1;i<=n;i++){
        vis[i]=0;
        la_e[i]=fir[i];
        dep[i]=1e9;
    }
    int pdt=0;
    dep[s]=0;
    head=0,tail=1;
    l[1]=s;
    while(head<tail){
        int now=l[++head];
        vis[now]=0;
        for(int i=fir[now];i;i=net[i]){
            int p=poi[i];
            if(dep[p]==1e9&&val[i]){
                dep[p]=dep[now]+1;
                if(p==t){
                    return 1;
                }
//              {pdt=1;continue;}
                if(vis[p])continue;
                l[++tail]=p;
                vis[p]=1;
            }
        }
    }
    return pdt;
}
ll dfs(int x,ll flow){
    if(x==t){
        ans+=flow;
        return flow;
    }
    if (flow==0) return 0;
    ll used=0;
    for(int i=la_e[x];i&&flow;i=net[i]){
        la_e[x]=i;//当前弧优化 
        int p=poi[i];
        if(dep[p]==dep[x]+1&&val[i]){
            ll nf=0;
            if(nf=dfs(p,min(flow-used,val[i]))){
                val[i]-=nf;
                val[i^1]+=nf;
                used+=nf;
                flow-=nf;
                if (flow==0) break;
                // if(used==nf)return used;
            }
            else dep[p]=1e9;
        }
    }
    return used;
}
void dinic(){
    while(bfs()){
        dfs(s,1e9);
    }
    return;
}
int main(){
    n=re(),m=re(),s=re(),t=re();
    for(int i=1;i<=m;i++){
        int x1=re(),x2=re(),x3=re();
        add(x1,x2,x3);
        add(x2,x1,0);
    }
    dinic();
    printf("%lld\n",ans);
    return 0;
}

by 方123456 @ 2022-08-11 09:10:40

@yangshiyu10

by yangshiyu10 @ 2022-08-11 09:39:14

@方123456 谢谢大佬，找到慢的地方了