Calanosay @ 2021-04-20 19:54:27
bool bfs(){
queue<int> q;
q.push(s);
memset(dis,-1,(n+1)*sizeof(int));
dis[s]=0;
noww[s]=head[s];
while(!q.empty()){
int node=q.front();q.pop();
for(int i=head[node];i!=-1;i=nex[i]){
int to=v[i];
if(dis[to]==-1&&w[i]){
dis[to]=dis[node]+1;
q.push(to);
noww[to]=head[to];
}
}
}
return dis[t]!=-1;
}
ll dfs(int x,ll flo){
if(x==t) return flo;
ll now=flo;
for(int i=noww[x];i!=-1;i=nex[i]){
noww[x]=i;
int to=v[i];
if(dis[to]==(dis[x]+1)&&w[i]){
ll d=dfs(to,min(now,w[i]));
now-=d;
w[i]-=d,w[i^1]+=d;
if(!now) break;
}
}
return flo-now;
}
每次dfs通一条路之后now数组都会重置,但是在你dfs的时候不是只会一直往下面搜索吗,我理解now数组的作用是在你遍历到now[x],x这个结点的时候起到一个传送作用,但是既然你是一直往后搜索,等于你dfs之后无法再次遍历到x这个结点了,也就是无法传送了。。所以我哪里理解有错误,这个优化明明很好,但我不理解
by wheneveright @ 2021-04-20 20:01:45
因为你这次经过了这条边,如果这条边是属于一个增广路的,那么它被选择了一定可以把它的能力全部发挥,而如果这一次都经过它,但是没有增广路那么下一次更不可能会用到它
by Calanosay @ 2021-04-20 20:06:25
@wheneveright 这我是明白的,我只是有些疑惑它的原理。。。这个优化是不是在稠密图作用明显呢?我觉得这个操作在一条路可以直接走到通,没有分叉的情况下是没有作用的。
by wheneveright @ 2021-04-20 20:08:00
@Fucker_Chao 它防的就是这种情况
by Calanosay @ 2021-04-20 20:09:09
@wheneveright 好的谢谢.
by wheneveright @ 2021-04-20 20:09:15
@Fucker_Chao 在稀疏途中加不加优化都无所谓,但是在部分稠密图可以把复杂度优化到
by hly1204 @ 2021-04-20 20:15:59
无重边的话好像确实不用考虑
by hly1204 @ 2021-04-20 20:22:37
因为你是多路,所以无重边确实无所谓的,只要保证一次是