为何一直RE三个点?

P3376 【模板】网络最大流

lindongli2004 @ 2018-12-31 19:49:00

代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long//int都成了long long
using namespace std;
const int M=2002019,N=200017,inf=1e15+7;//如此大的范围
int ans,n,m,s,t,dep[N],stk[N];
struct Edge{
    int from,to,next,data;
}e[M<<1];int v[N],tot;
void add_real(int x,int y,int z)
{
    e[tot].from=x;
    e[tot].to=y;
    e[tot].data=z;
    e[tot].next=v[x];
    v[x]=tot;++tot;
}
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool bfs()
{
    for(int i=1;i<=n;i++)dep[i]=-1;
    dep[s]=0;
    int head(1),tail(0);
    stk[++tail]=s;
    while(head<=tail)
    {
      int w=stk[head++];
      for(int p=v[w];p!=-1;p=e[p].next)
      {
        int kp=e[p].to;
        if(dep[kp]==-1 && e[p].data>0)
        {
          dep[kp]=dep[w]+1;
          stk[++tail]=kp;
        }
      }
    }
    if(dep[t]<0)return false;
    return true;
}
int dfs(int x,int exp)
{
    if(x==t)return exp;
    int tmp=0,flow=0;
    for(int p=v[x];p!=-1;p=e[p].next)
    {
      int kp=e[p].to;
      if(dep[kp]==dep[x]+1 && e[p].data>0)
      {
        tmp=dfs(kp,min(exp,e[p].data));
        if(!tmp)continue;
        exp-=tmp;
        flow+=tmp;
        e[p].data-=tmp;
        e[p^1].data+=tmp;
        if(!exp)break;
      }
    }
    return flow;
}
#undef int
int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=0;i<=m*3;i++)e[i].next=v[i]=-1;
    for(int i=1;i<=m;i++){
        long long a=read(),b=read(),c=read();
        add_real(a,b,c);add_real(b,a,0);
    }
    while(bfs())
      ans+=dfs(s,inf);
    cout<<ans<<endl;
    return 0;
}

我想知道:why?


by NULL0x7f @ 2019-01-22 13:09:04

同问


|