EK不过样例52pts求助

P3376 【模板】网络最大流

hamster000 @ 2024-03-20 00:15:00

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=100005;
const int N=1005;
int h[N],v[M],w[M],nxt[M];
int mf[N],pre[N];
int idx=1;
void add(int a,int b,int c){
    v[++idx]=b;
    w[idx]=c;
    nxt[idx]=h[a];
    h[a]=idx;
}
int n,m,S,T;
bool bfs(){
    memset(mf,0,sizeof(mf));
    mf[S]=1e9;
    queue<int> q;
    q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=nxt[i]){
            if(!mf[v[i]]&&w[i]){
                mf[v[i]]=min(mf[u],w[i]);
                pre[v[i]]=i;
                q.push(v[i]);
                if(v[i]==T){
                    return 1;
                }

            }

        }
    }
    return 0;
}
ll EK(){
    ll flow=0;
    while(bfs()){
        int tmp=T;
        while(tmp!=S){
            int i=pre[tmp];
            w[i]-=mf[tmp];
            w[i^1]+=mf[tmp];
            tmp=v[i^1];
        }
        flow+=mf[T];
    }
    return flow;
}

int main(){
    cin >> n >> m >> S >> T;
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,0);
    }
    cout << EK() << endl;
}

by L_zaa_L @ 2024-03-20 08:24:33

@hamster000

w[i]-=mf[tmp];
w[i^1]+=mf[tmp];

应该减去 mf[T]


by __Cby___ @ 2024-03-20 12:29:36

w[i]-=mf[tmp];
w[i^1]+=mf[tmp];

变成

w[i]-=mf[T];
w[i^1]+=mf[T];

by hamster000 @ 2024-03-20 22:50:09

@__Cby___ 怪我眼瞎没跳出来,谢了各位。


|