求各位大佬看看为什么过不了#5

P3376 【模板】网络最大流

华容 @ 2019-06-23 16:03:24

求大佬看看为什么过不了#5

#include<bits/stdc++.h>
using namespace std;
int head[1000001],to[1000001],w[1000001],next[1000001],increase,deth[1000001],h[1000001],INT=0xffffff7;
int num=1,S,M,N,T,an,id;
queue <int> q;
void add(int a,int b,int c)
{
    next[++num]=head[a];
    head[a]=num;
    to[num]=b;
    w[num]=c;
}
int main()
{
    ifstream fin("123.in");
    int s,e,c,j,k;
    int ui,vi,wi;//ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
    int i;
    fin>>N>>M>>S>>T;//分别表示点的个数、有向边的个数、源点序号、汇点序号.
    for(i=1;i<=M;i++)
    {
        fin>>ui>>vi>>wi;
        add(ui,vi,wi);
        add(vi,ui,0);
    }
    while(1)
    {
        while(!q.empty())
        {
            q.pop();
        }
        memset(h,0,sizeof (h));
        memset(deth,0,sizeof(deth));
        q.push(S);
        deth[S]=INT;
        while(!q.empty())
        {
            s=q.front();
            q.pop();
            if(s==T)
            {
                break;
            }
            for(e=head[s];e!=0;e=next[e])
            {
                c=to[e];
                if(h[c]==0&&w[e]>0)
                {
                    h[c]=s;
                    q.push(c);
                    deth[c]=min(w[e],deth[s]);
                }
            }
        }
        if(h[T]==0)
        {
            break;
        }
        j=T;
        while(j!=S)
        {
            for(k=head[j];k!=0;k=next[k])
            {
                if(to[k]==h[j])
                {
                    w[k]+=deth[T];
                    w[1^k]-=deth[T];
                    break;
                }
            }
            j=h[j];

        }
        an=an+deth[T];
    }
    cout<<an;
}

|