求dalao指教一下,为什么样例我输出的是20

P3376 【模板】网络最大流

huangx607087 @ 2019-08-06 22:46:40

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,A;
int e[950000],w[950000],hd[950000],nxt[950000];
int q[3350000],step[950000];
bool bfs()
{
    int f=1,r=1;
    memset(q,0,sizeof(q));
    memset(step,0,sizeof(step));
    step[s]=1,q[1]=s;
    while(f<=r)
    {
        int x=q[f++],k=hd[x];
        while(k)
        {
            if(step[e[k]]==0&&w[e[k]]>0)
            {
                step[e[k]]=step[x]+1;
                q[++r]=e[k];
            }
            k=nxt[k];
        }
    }
    return step[t];
}
int dfs(int x,int flow)
{
    if(x==t) return flow;
    int k=hd[x];
    while(k)
    {
        if(w[k]&&step[e[k]]==step[x]+1)
        {
            int dis=dfs(e[k],min(flow,w[k]));
            if(dis>0)
            {
                w[k]-=dis;
                if(k%2) w[k+1]+=dis;
                else w[k-1]+=dis;
                return dis;
            }
        }
        k=nxt[k];
    }
    return 0;
}
void dinic()
{
    int B=0;
    while(bfs())
    {
        while(B=dfs(s,20011230)) A+=B;
    }
}
int main()
{
    int i,j,k=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[++k]=y,w[k]=z,nxt[k]=hd[x],hd[x]=k;
        e[++k]=x,w[k]=0,nxt[k]=hd[y],hd[y]=k;
    }
    dinic();
    printf("%d\n",A);
    return 0;
}

by Vn_nV @ 2019-08-06 22:48:15

自己调


|