求大佬查错

P3376 【模板】网络最大流

AThousandSuns @ 2018-02-04 18:04:22

如题,下面这个程序wa3,4,5

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
    int to,cap,flow,nxt;
}e[200200];
int n,m,s,t,head[10010],el,dis[10010],cur[10010];
bool vis[10010];
int read(){
    char ch;
    while((ch=getchar()) && !isdigit(ch));
    int sum=ch-'0';
    while((ch=getchar()) && isdigit(ch)) sum=sum*10+ch-'0';
    return sum;
}
void add(int u,int v,int c){
    e[++el]=(edge){v,c,0,head[u]};
    head[u]=el;
}
bool bfs(){
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    dis[s]=0;
    vis[s]=true;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int fnode=q.front();
        for(int i=head[fnode];i;i=e[i].nxt){
            int tnode=e[i].to;
            if(!vis[tnode] && e[i].cap>e[i].flow){
                dis[tnode]=dis[fnode]+1;
                vis[tnode]=true;
                q.push(tnode);
            }
        }
        q.pop();
    }
    return vis[t];
}
int dfs(int fnode,int minres){
    if(fnode==t || minres==0) return minres;
    int rtf=0,f;
    for(int &i=cur[fnode];i;i=e[i].nxt){
        int tnode=e[i].to;
        if(dis[fnode]+1==dis[tnode] &&(f=dfs(tnode,min(minres,e[i].cap-e[i].flow)))>0){
            e[i].flow+=f;
            e[i^1].flow-=f;
            rtf+=f;
            minres-=f;
            if(minres==0) break;
        }
    }
    return rtf;
}
int main(){
    int i;
    n=read();m=read();s=read();t=read();
    for(i=1;i<=m;i++){
        int u,v,c;
        u=read();v=read();c=read();
        add(u,v,c);
        add(v,u,0);
    }
    int flow=0;
    while(bfs()){
        for(i=1;i<=n;i++) cur[i]=head[i];
        flow+=dfs(s,2147483647);
    }
    printf("%d\n",flow);
}

by yyy14159 @ 2018-02-04 18:23:33

DFS里给反边减去流f的时候 i^1不是i的反边吧。 1^1=0 但你编号为1的边的反边是编号为2的边啊


by AThousandSuns @ 2018-02-04 21:18:44

@yyy14159 哇,原来是这里啊,感谢大佬


|