dinic算法91分 第9个点莫名其妙TLE 求调

scyFBM @ 2023-01-11 16:13:30

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=209;
const int M=5009;
int n,m,s,t;
int dis[N];
struct edge{
    int l,r,c;
    int nxt;
}e[M*2];
int hed[N],ecnt=2;
void add(int l,int r,int c){
    e[ecnt].l=l;
    e[ecnt].r=r;
    e[ecnt].c=c; 
    e[ecnt].nxt=hed[l];
    hed[l]=ecnt;
    ecnt++; 
}
bool bfs(){
    queue<int> q;
    for(int i=1;i<=n;i++) dis[i]=-1;
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        for(int i=hed[cur];i;i=e[i].nxt){
            if(dis[e[i].r]==-1&&e[i].c>0){
                dis[e[i].r]=dis[cur]+1;  
                q.push(e[i].r);
            }
        }
    }
    return(dis[t]!=-1);
}
int dfs(int start,int flow){
    int cnt=0; 
    if(start==t) return flow;
    for(int i=hed[start];i&&flow;i=e[i].nxt){ 
        if((e[i].c>0)&&(dis[e[i].r]==dis[start]+1)){
            int ret=dfs(e[i].r,min(flow,e[i].c)); 
            if(ret>0){
                e[i].c-=ret; 
                if(i&1) e[i-1].c+=ret;
                else e[i+1].c+=ret;
                cnt+=ret;
                flow-=ret; 
            }
        }
    }   
    return cnt; 
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    int ans=0;
    while(bfs()) ans+=dfs(s,1e9);
    cout<<ans<<endl;
    return 0;
}

by lzyqwq @ 2023-01-11 16:39:06

@shenchengyue 加个裆前弧优化试试

by sinsop90 @ 2023-01-11 16:39:35

dfs里面return cnt前面加一个

if(!cnt) dis[start] = -1;

by sinsop90 @ 2023-01-11 16:39:52

@shenchengyue

by sinsop90 @ 2023-01-11 16:40:35

当前点后面没有增广路的话之后就不用遍历这个点了

by scyFBM @ 2023-01-11 16:40:51

@蒟蒻·廖子阳 但是我觉得TLE的原因还是触发死循环了

by scyFBM @ 2023-01-11 16:41:35

哦我试试吧谢谢奆佬

by _saltFish_ @ 2023-01-11 16:41:36

@shenchengyue bfs函数里

if(dis[e[i].r]==-1&&e[i].c>0){
    dis[e[i].r]=dis[cur]+1;  
    q.push(e[i].r);
}

在最后加上 if(e[i].r == t) return 1;

by scyFBM @ 2023-01-11 16:45:24

@JR_ytxy 哦我再试试

by lzyqwq @ 2023-01-11 16:45:33

@shenchengyue 并不是，我的 dinic 常用模板都是加了炸点和当前弧（有了后者前者只是小优化）。

bool bfs(){
    memset(d,0,sizeof d);
    memcpy(now,hd,sizeof hd);
    d[q[h=t=1]=0]=1;
    while(h<=t){
        int x=q[h++];
        for(int i=hd[x];i;i=e[i].ne){
            if(e[i].w&&!d[e[i].v]){
                d[q[++t]=e[i].v]=d[x]+1;
                if(e[i].v==T){
                    return 1;
                }
            }
        }
    }
    return 0;
}
int dfs(int x,int f){
    if(x==T){
        return f;
    }
    int s=0,g;
    for(int i=now[x];i;i=e[i].ne){
        if(e[i].w&&d[e[i].v]==d[x]+1){
            s+=(g=dfs(e[i].v,min(f-s,e[i].w)));
            e[i].w-=g;
            e[i^1].w+=g;
            if(s==f){
                now[x]=i;
                return s;
            }
        }
    }
    now[x]=d[x]=0;
    return s;
}

by _saltFish_ @ 2023-01-11 17:00:32

@shenchengyue 破案了，加上当前弧优化就能过。常数问题。