刚学网络流求助 一直TLE出不了答案

P3376 【模板】网络最大流

odt03 @ 2023-01-09 16:57:14

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
struct Edge{
    int to,next,flow;
}edge[10010];
int head[210],dep[210];
int tot=1,s,t;
void add(int from,int to,int flow){
    edge[++tot].to=to,edge[tot].next=head[from],edge[tot].flow=flow;
    head[from]=tot;
    edge[++tot].to=from,edge[tot].next=head[to],edge[tot].flow=0;
    head[to]=tot;
}
bool bfs(){
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(s),dep[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to,f=edge[i].flow;
            if(dep[v]==0&&f>0){
                q.push(v);
                dep[v]=dep[u]+1;
                if(v==t)return true;
            }
        }
    }
    return false;
}
int dfs(int u,int flow){
    if(u==t){
        return flow;
    }
    int rest=flow;
    for(int i=head[u];i&&rest;i=edge[i].next){
        int v=edge[i].to,f=edge[i].flow;
        if(dep[v]==dep[u]+1&&f>0){
            int ff=dfs(v,min(rest,f));
            if(ff=0)dep[v]=0;
            rest-=ff;
            edge[i].flow-=ff;
            edge[i^1].flow+=ff;
        }
    }
    return flow-rest;
}
int Dinic(){
    int mxf=0,flow;
    while(bfs()){
        while(flow=dfs(s,INF)){
            mxf+=flow;
        }
    }
    return mxf;
}
int main(){
    int n,m;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<Dinic()<<endl;
    return 0;
} 

by maxyzfj @ 2023-01-09 17:08:27

dfs里if(ff=0)dep[v]=0;改成if(ff==0)dep[v]=0;试一下


by odt03 @ 2023-01-09 17:15:35

谢谢(眼睛瞎了)


|