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
这位是