萌新求助EK

P3376 【模板】网络最大流

Rolling_L @ 2021-07-08 10:41:31

RT

不知道为什么在图的规模较大时会WA,与网上同类型代码对比无果。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
int g[205][205];
queue<int> q;
bool vis[205];
int pre[205];
int bfs(){
    memset(vis,0,sizeof(vis));
    memset(pre,0,sizeof(pre));
    while(q.size()){
        q.pop();
    }
    q.push(s);
    vis[s]=1;
    int res=0x3f3f3f3f;
    while(q.size()){
        int u=q.front();
        q.pop();
        if(u==t)break;
        for(int i=1;i<=n;i++){
            int v=i;
            if(!vis[v]&&g[u][v]>0&&u!=v){
                res=min(g[u][v],res);
                pre[v]=u;
                vis[v]=1;
                q.push(v);
            }
        }
    }
    if(pre[t]){
        return res;
    }else{
        return 0;
    }
}
void renew(int u,int w){
    while(u!=s&&pre[u]){
        g[u][pre[u]]+=w;
        g[pre[u]][u]-=w;
        u=pre[u];
    }
}
int EK(){
    int now=0,res=0;
    do{
        now=bfs();
        renew(t,now);
        res+=now;
    }while(now);
    return res;
}

signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v]=w;
    }
    cout<<EK();
    return 0;
}

|