ningago @ 2022-03-19 13:42:31
看到很多大佬都这么写dfs:
//
//
//
//
ll dfs(ll k,ll c)
{
ll res = 0;
if(k == T)
return c;
for(ll i = cur[k];~i && c;i = ne[i])
{
cur[k] = i;
ll nx = e[i];
if(ceng[nx] == ceng[k] + 1 && w[i])
{
ll t = dfs(nx,min(w[i],c));
if(!t)
ceng[nx] = -1;
w[i] -= t;
w[i ^ 1] += t;
res += t;
c -= t;
}
}
return 0;
}
而蒟蒻我是这么写的:
ll dfs(ll k,ll c)
{
if(k == T)
return c;
for(ll i = cur[k];~i;i = ne[i])
{
cur[k] = i;
ll nx = e[i];
if(ceng[nx] == ceng[k] + 1 && w[i])
{
ll t = dfs(nx,min(w[i],c));
if(t > 0)
{
w[i] -= t;
w[i ^ 1] += t;
return t;
}
}
}
return 0;
}
我这个写法是不是有什么问题或确点啊
by yzh_Error404 @ 2022-03-19 13:45:25
没有炸边,下一次还会走这条边?
by ningago @ 2022-03-19 13:46:43
@yzh_Error404
有当前弧不会再走了吧?
by Foreverxxx @ 2022-03-19 13:51:42
流出量为
by ningago @ 2022-03-19 13:54:51
@Foreverxxx
%%% 那后面的写法在 if(t>0) 前面加上 if(!t) ceng[nx] = -1;会和上面一样吗?
by Foreverxxx @ 2022-03-19 14:04:27
@ningago 对的,如果流不出去,直接设置层数使得不会再次遍历到这条边就行了。
by ningago @ 2022-03-19 14:09:05
@Foreverxxx 蟹蟹