蒟蒻求出 EK 19pts WA

P3376 【模板】网络最大流

wtcqwq @ 2022-01-24 10:02:42

rt

哪位大佬帮我调一下,非常感谢

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=200009;
const ll N=50009;
struct edge{
    ll to,c,nxt;
}e[M*2];
ll flow[N],pre[N];
ll hd[N];
ll S,T,nE=1,n,m;
const ll INF=1e9;
void add(ll u,ll v,ll c){
    e[++nE]=(edge){v,c,hd[u]};
    hd[u]=nE;
} 
bool bfs(){
    fill(pre,pre+1+n,0);
    queue<ll> q;
    q.push(S);
    pre[S]=-1;
    flow[S]=INF;
    while(!q.empty()){
        ll u=q.front(); q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            ll c=e[i].c;
            if(!c)continue;
            ll v=e[i].to;
            if(pre[v])continue;
            q.push(v);
            pre[v]=i;
            flow[v]=min(flow[u],c);
            if(v==T)return 1;
        }
    }
    return 0;
}
void EdmondKarp(){
    ll maxFlow=0;
    while(bfs()){
        maxFlow+=flow[n];
        for(int u=T;u!=S;u=e[pre[u]^1].to){
            e[pre[u]].c-=flow[T];
            e[pre[u]^1].c+=flow[T]; 
        }
    }
    cout<<maxFlow<<endl;
}
int main(){
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
        ll u,v,c;
        cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,0);
    }
    EdmondKarp();
    return 0;
}

by Code_AC @ 2022-01-24 10:09:50

@王韬淳 您会用Dinic吗?您用Dinic吧


by Code_AC @ 2022-01-24 10:12:08

@王韬淳 【模板】网络最大流 您可以看一眼


by wtcqwq @ 2022-01-24 10:15:41

@撤硕____ 哦 我会用Dinic 就是想把其他方法也学一学。不过非常感谢


by Code_AC @ 2022-01-24 10:18:09

@王韬淳 主要是本蒟蒻也不会EK,其实会Dinic就可以了,比EK要好


by wtcqwq @ 2022-01-24 10:28:49

好 谢谢


|