萌新求助,有3个点为何RE呀QWQ

P3376 【模板】网络最大流

Sai0511 @ 2018-10-04 20:51:14

#include<bits/stdc++.h>  
#define gc getchar    
const int MAXN=200010;
const int MAXM=200010;
const int INF=0x7f7f7f7f;
using namespace std;   
int n,m,i,j,x,y,z,cnt=1,Beg,End,ans,tot;
struct Pre{int side,pre;};
Pre pre[MAXM];
int head[MAXM];
struct Edge{int to,val,nxt;};  
Edge g[MAXM];   
bool vis[MAXM];
void addEdge(int u,int v,int val){
    g[++cnt].to=v;
    g[cnt].val=val;
    g[cnt].nxt=head[u];
    head[u]=cnt;  
}    
struct io{
    int read(){
        int x=0;char c;
        for(c=gc();!isdigit(c);c=gc()) ;
        for(;isdigit(c);c=gc()) x=x*10+c-48;
        return x;
    }
}Fio;
#define read Fio.read  
queue<int>q;   
bool bfs(){
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    vis[Beg]=1;while(!q.empty()) q.pop();q.push(Beg);
    tot++;
    while(!q.empty()){
        int u=q.front();q.pop();
        //cout << u << endl;
        for(int i=head[u];i;i=g[i].nxt){
            int to=g[i].to;
        //  cout << g[i].to<<' '<<g[i].val << endl;
            if(vis[to]||g[i].val==0) continue;   
        //  cout << to <<' '<<g[to].val << endl;
            vis[to]=1;
            pre[to].side=i;
            pre[to].pre=u;      
        //  cout << to << endl;
            if(to==End) {return 1;}
            q.push(to);
            //while(!q.empty()) q.pop();
        }
    }
    //cout << 1 << endl;
    return 0;
}   
int EK(){
    int ans=0;
    while(1){
        bool f=bfs();
    //  cout << f << endl;
        if(!f) break;
        int i,j;     
        int Min=INF;
        //cout << 1 << endl;
        for(i=End;i!=Beg;i=pre[i].pre)
         Min=min(Min,g[pre[i].side].val);   
        //cout << Min << endl; 
        for(i=End;i!=Beg;i=pre[i].pre){
            g[pre[i].side].val-=Min;
            g[pre[i].side^1].val+=Min;    
        //  cout << i << endl;
        }
        ans+=Min;         
        //cout << ans << endl;
    }
    return ans;
}
int main(){
    n=read();m=read();Beg=read();End=read();   
    for(i=1;i<=m;i++){
        int u=read(); int v=read(); int l=read();
        addEdge(u,v,l);
        addEdge(v,u,0);
    }
    //for(i=head[Beg];i;i=g[i].nxt) cout << g[i].to << ' '<<g[i].val << endl;
    ans=EK();   
    printf("%d\n",ans);
}

|