tle求助!!难道要卡常??

P3376 【模板】网络最大流

pengze36 @ 2024-12-07 10:17:24

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long 
using namespace std;
int n,m,s,t;
bool vis[2100];
int head[2100],ver[100005],nnext[100005];
int  c[100005];
int tot;
inline void add(int x,int y,ll cx){
    ver[++tot]=y;
    nnext[tot]=head[x];
    head[x]=tot;
    c[tot]=cx;
}
inline int dfs(int u,int  minf){
    if(u==t||minf==0) return minf;
    vis[u]=1;
    for(int i=head[u];i;i=nnext[i]){
        int v=ver[i];
        if(c[i]&&(!vis[v])){
            int f=dfs(v,min(minf,c[i]));
        if(f>0){
            c[i]-=f;
            if(i&1) c[i+1]+=f;
            else c[i-1]+=f;
            return f;
        }
        }
    }
    return 0;
}
inline ll FF(){
    ll maxflow=0;
    while(1){
        memset(vis,0,sizeof vis);
        ll f=dfs(s,0x3f3f3f3f3f3f3f3f);
        if(f==0) break;
        maxflow+=(ll)f;
    }
    return maxflow;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for( int i=1;i<=m;++i){
        int u,v;
        int w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
    }
    printf("%lld\n",FF());
    return 0;
} 

by yanmingqian @ 2024-12-07 10:19:30

@pengze36 FF时间复杂度无法通过此题


|