神奇的语句 !!!!!

P3376 【模板】网络最大流

wret4d @ 2018-10-31 23:05:36

代码里我上注释的一行为什么一定要加,不加就会RE三个点,0应该不会影响,而且也没有负值,求巨佬们解读。 以下为代码及注释

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
int n,m,s,tt,q[200010],w[200010],e[200010],r[200010],t[200010],dep[10010],f[200010];
queue <int> qq;

bool bfs()
{
    memset(dep,0,sizeof(dep));
    while(qq.size())
    {
        qq.pop();
    }
    qq.push(s);
    dep[s]=1;
    while(qq.size()!=0)
    {
        int x=qq.front();
        qq.pop();
        for(int i=r[x];i!=0;i=t[i])
        {
            if(dep[w[i]]==0&&e[i]>f[i])
            {
                dep[w[i]]=dep[x]+1;
                qq.push(w[i]);
            }
        }
    }
    return dep[tt];
}
int dfs(int x,int F)
{
    if(x==tt)
    {
        return F;
    }
    int ret=0;
    for(int i=r[x];i!=0;i=t[i])
    {
        if(dep[w[i]]==dep[x]+1&&e[i]>f[i])
        {
            int di=dfs(w[i],min(F,e[i]-f[i]));
            if(di>0)//为什么一定要加上这句话? 
            {
                f[i]+=di;
                f[i+m]-=di;
                ret+=di;
                F-=di;
            }
        }
    }
    return ret;
}
void dnic()
{
    int ret=0;
    while(bfs())
    {
        ret+=dfs(s,1e6);
    }   
    printf("%d",ret);
    return ;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&tt);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q[i],&w[i],&e[i]);
        q[i+m]=w[i];
        w[i+m]=q[i];
    }
    for(int i=1;i<=m<<1;i++)
    {
        t[i]=r[q[i]];
        r[q[i]]=i;
    }
    dnic();
    return 0;
}

by tocek_shiki @ 2018-10-31 23:06:43

F-=di


by prophetB @ 2018-10-31 23:59:58

会影响,不加可能会dfs不停

虽然我不是这么写的


by prophetB @ 2018-11-01 00:00:27

不同的写法要求不同


by SSerxhs @ 2018-11-01 01:13:12

只要写不等就可以了


by SSerxhs @ 2018-11-01 01:13:36

另外没事不用把流过的和总流量分开写


by Dispwnl @ 2018-11-01 06:59:59


by interestingLSY @ 2018-11-01 07:10:58

@prophetB 对对对这位dalao说得对


by prophetB @ 2018-11-01 09:36:48

@interestingLSY
这位是L省的红太阳

\color{red}{AK}\color{black}NOIPLNOINOIIOIAPIOCTSC

|