Dinic全TLE求助

P3376 【模板】网络最大流

快斗游鹿 @ 2023-01-23 22:37:40

RT,本地测没问题,交上去全 TLE。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20500;
struct edge{
    int to,nxt,w;
}e[N*2];
int n,m,s,t,cnt=1,head[N];
int dep[N],flag[N],ans;//dep深度,flag是否在队列中 
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
bool bfs(){//分层 
    memset(dep,0,sizeof(dep));
    memset(flag,0,sizeof(flag));
    queue<int>q;
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        flag[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].w;
            if(!dep[v]&&w){
                dep[v]=dep[u]+1;
                if(!flag[v]){
                    q.push(v);flag[v]=1;
                }
            }
        }
    }
    if(dep[t])return 1;
    return 0;
}
int dfs(int u,int flow){//找增广路 
    int rlow=0;
    if(u==t)return flow;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(w&&dep[v]==dep[u]+1){
            if(rlow=dfs(v,min(flow,w))){
                e[i].w-=rlow;
                e[i^1].w+=rlow;
                return rlow;
            }
        }
    }
}
void Dinic(){
    int lowflow;
    while(bfs()){
        while(lowflow=dfs(s,1145141919810))ans+=lowflow;
    }
}
signed main(){
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        int u,v,w;u=read();v=read();w=read();
        add(u,v,w);add(v,u,0);//正向边&反向边 
    }
    Dinic();
    printf("%lld",ans);
    return 0;
}

by bamboo12345 @ 2023-01-24 10:14:31

@TheSky233 那EK是个啥如果多路增广只是优化


by TheSky233 @ 2023-01-24 10:23:51

@bamboo123 楼主的代码和 EK 的区别就是他的代码用了 分层图 了啊,比方说

显然的 EK 可能会增广 1998 次,但是 dinic 分层之后只要增广两次


by bamboo12345 @ 2023-01-24 10:43:38

@TheSky233 不不不这不是FF算法吗?


by TheSky233 @ 2023-01-24 10:47:04

@bamboo123 EK 就是用 bfs 找增广路的 FF...


by bamboo12345 @ 2023-01-24 10:54:15

@TheSky233 行吧,是我孤陋了


上一页 |