ZnO34 @ 2020-08-22 11:38:50
萌新刚学 OI 当前弧优化，有一点小疑问。
假如有下面这张图，采用当前弧优化之后，会在从点 1 访问到点 3 的时候，遍历点 3 的所有出边，并且会把 3 --> T 的边变成废边（访问不到的边）。
然后从点 2 访问到点 3 的时候，遍历点 3 的出边的时候就没有 3 --> T 这条边了，又要等待下一次 dfs 才能增广。这算不算当前弧的负优化？
by UltiMadow @ 2020-08-22 11:43:50
建议重学当前弧？
by UltiMadow @ 2020-08-22 11:44:30
3->T 没增广完不会被废啊
by Smile_Cindy @ 2020-08-22 11:55:42
@jiyu596
当前弧优化在没有增广完毕的时候是不会将该边变废的。
int DFS(int v,int t,int flow)
{
if(v==t)return flow;
for(int &i=head[v];i!=-1;i=E[i].nxt)
{
int to=E[i].v,cap=E[i].cap;
if(cap>0 && dis[to]==dis[v]+1)
{
int ret=DFS(to,t,min(flow,cap));
if(ret>0)
{
E[i].cap-=ret;
E[i^1].cap+=ret;
return ret;
}
}
}
return 0;
}例如这段代码，当第一次访问3->T之后已经return了，就不会把该边变废。
by ZnO34 @ 2020-08-22 14:44:51
@Alpha 您的代码中，第一次访问之后直接 return，是不是不能多路同时增广？（EK？）多路同时增广和当前弧可以一起用吗？
（我是看的本题第一篇题解和洛谷日报的代码）
以第一篇题解中的代码为例，此代码似乎（初学，说错了轻喷）可以多路同时增广：
inline int dfs(int x,long long sum) { //sum是整条增广路对最大流的贡献
if(x==t) return sum;
long long k,res=0; //k是当前最小的剩余容量
for(register int i=now[x];i&∑i=e[i].net) {
now[x]=i; //当前弧优化
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf; //剪枝，去掉增广完毕的点
e[i].val-=k;
e[i^1].val+=k;
res+=k; //res表示经过该点的所有流量和（相当于流出的总量）
sum-=k; //sum表示经过该点的剩余流量
}
}
return res;
}这里面没有 return ……
真的非常感谢您抽空来看看我的问题！
by ZnO34 @ 2020-08-22 14:48:27
@UltiMadow 可否给出一个比较好的学当前弧的地址？似乎本篇的第一篇题解
inline int dfs(int x,long long sum) { //sum是整条增广路对最大流的贡献
if(x==t) return sum;
long long k,res=0; //k是当前最小的剩余容量
for(register int i=now[x];i&∑i=e[i].net) {
now[x]=i; //当前弧优化
int v=e[i].to;
if(e[i].val>0&&(dis[v]==dis[x]+1)) {
k=dfs(v,min(sum,e[i].val));
if(k==0) dis[v]=inf; //剪枝，去掉增广完毕的点
e[i].val-=k;
e[i^1].val+=k;
res+=k; //res表示经过该点的所有流量和（相当于流出的总量）
sum-=k; //sum表示经过该点的剩余流量
}
}
return res;
}没增广完就被废了…… 更大的可能是我理解错了 /笑哭 感谢回复！
by UltiMadow @ 2020-08-22 15:12:16
@jiyu596 没费啊/youl
now 又不是指向next（
by zhangtianhan @ 2020-09-08 18:34:59
@jiyu596 理解的不对，虽然这个代码没有return，但是for循环条件里带上了sum，所以sum=0后就会直接退出循环然后return