蒟蒻求助qwq

P3376 【模板】网络最大流

Isprime @ 2019-08-16 16:14:25

#include<cstdio>
#include<queue>
#include<algorithm>
#define MAXN 10001
#define MAXM 200001
#define ri register int
#define INF 0x7ffffff
using namespace std;
queue<int> q;
int n,m,s,t,edge_sum,maxflow;
int head[MAXM],pre[MAXN],flow[MAXN];
struct Edge{
    int next,to,dis;
}edge[MAXM];
inline void addedge(int from,int to,int dis){
    edge[++edge_sum].next=head[from];
    edge[edge_sum].to=to;
    edge[edge_sum].dis=dis;
    head[from]=edge_sum;
}
inline int bfs(int s,int t){
    while(!q.empty()) q.pop();
    for(ri i=1;i<=n;i++) pre[i]=-1;
    pre[s]=0;
    q.push(s);
    flow[s]=INF;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(x==t) break;
        for(ri i=head[x];i;i=edge[i].next){
            if(pre[edge[i].to]==-1){
                pre[edge[i].to]=x;
                flow[edge[i].to]=min(flow[x],edge[i].dis);
                q.push(edge[i].to);
            }
        }
    }
    if(pre[t]==-1) return -1;
    else return flow[t];
}
inline void EK(int s,int t){
    int increase=0;
    while((increase=bfs(s,t))!=-1){
        int k=t;
        while(k!=s){
            int last=pre[k];
            for(ri i=head[last];i;i=edge[i].next){
                if(edge[i].to==k){
                    edge[i].dis-=increase;
                    break;
                }
            }
            for(ri i=head[k];i;i=edge[i].next){
                if(edge[i].to==last){
                    edge[i].dis+=increase;
                    break;
                }
            }
            k=last;
        }
        maxflow+=increase;
    }
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(ri x,y,z,i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        addedge(x,y,z);
        addedge(y,x,0);
    }
    EK(s,t);
    printf("%d\n",maxflow);
    return 0;
}

为什么程序运行到 pre[edge[i].to]=x;的时候死循环了?


by lvneg1 @ 2019-08-16 16:15:55

orz


|