EK算法死循环了,求助

P3376 【模板】网络最大流

simonG @ 2022-11-14 14:00:49

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=210,M=5010;
const LL inf=1e18;
int n,m,s,t,u,v;
int tot=1,head[N],ver[M*2],nxt[M*2],flag[N][N];
int pre[N];
LL edge[M*2],minv[N],w,ans;
bool vis[N];
void addedge(int x,int y,LL z) {
    ver[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}
bool bfs() {
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s); vis[s]=1; minv[s]=inf;
    for(; q.size(); ) {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=nxt[i]) {
            if(edge[i]==0) continue;
            int y=ver[i];
            if(vis[y]) continue;
            minv[y]=min(minv[y],edge[i]);
            pre[y]=i; q.push(y); vis[y]=1;
            if(y==t) return 1;
        }
    }
    return 0;
}
void update() {
    int x=t;
    for(; x!=s; ) {
        int v=pre[x];
        edge[v]-=minv[t];
        edge[v^1]+=minv[t];
        x=ver[v^1];
    }
    ans+=minv[t];
}
int main() {
    cin>>n>>m>>s>>t;
    for(int i=1; i<=m; i++) {
        cin>>u>>v>>w;
        if(flag[u][v]==0) {
            addedge(u,v,w);
            flag[u][v]=tot;
            addedge(v,u,0);
        } else {
            edge[flag[u][v]]+=w;
        }
    }
    for(; bfs(); ) {
        update();
    }
    cout<<ans<<endl;
    return 0;
}

by zesqwq @ 2022-11-14 14:09:18

minv[y]=min(minv[y],edge[i]); 错了


by zesqwq @ 2022-11-14 14:09:27

@gaosichensb


by CH_mengxiang @ 2022-11-21 22:47:25

head初始化为-1,循环条件由i改为~i


|