@[shenchengyue](/user/766405) 加个裆前弧优化试试
by lzyqwq @ 2023-01-11 16:39:06
dfs里面return cnt前面加一个
```
if(!cnt) dis[start] = -1;
```
by sinsop90 @ 2023-01-11 16:39:35
@[shenchengyue](/user/766405)
by sinsop90 @ 2023-01-11 16:39:52
当前点后面没有增广路的话之后就不用遍历这个点了
by sinsop90 @ 2023-01-11 16:40:35
@[蒟蒻·廖子阳](/user/539211) 但是我觉得TLE的原因还是触发死循环了
by scyFBM @ 2023-01-11 16:40:51
哦我试试吧谢谢奆佬
by scyFBM @ 2023-01-11 16:41:35
@[shenchengyue](/user/766405) bfs函数里
```cpp
if(dis[e[i].r]==-1&&e[i].c>0){
dis[e[i].r]=dis[cur]+1;
q.push(e[i].r);
}
```
在最后加上 `if(e[i].r == t) return 1;`
by _saltFish_ @ 2023-01-11 16:41:36
@[JR_ytxy](/user/661044) 哦我再试试
by scyFBM @ 2023-01-11 16:45:24
@[shenchengyue](/user/766405) 并不是,我的 `dinic` 常用模板都是加了炸点和当前弧(有了后者前者只是小优化)。
```cpp
bool bfs(){
memset(d,0,sizeof d);
memcpy(now,hd,sizeof hd);
d[q[h=t=1]=0]=1;
while(h<=t){
int x=q[h++];
for(int i=hd[x];i;i=e[i].ne){
if(e[i].w&&!d[e[i].v]){
d[q[++t]=e[i].v]=d[x]+1;
if(e[i].v==T){
return 1;
}
}
}
}
return 0;
}
int dfs(int x,int f){
if(x==T){
return f;
}
int s=0,g;
for(int i=now[x];i;i=e[i].ne){
if(e[i].w&&d[e[i].v]==d[x]+1){
s+=(g=dfs(e[i].v,min(f-s,e[i].w)));
e[i].w-=g;
e[i^1].w+=g;
if(s==f){
now[x]=i;
return s;
}
}
}
now[x]=d[x]=0;
return s;
}
```
by lzyqwq @ 2023-01-11 16:45:33
@[shenchengyue](/user/766405) 破案了,加上当前弧优化就能过。常数问题。
by _saltFish_ @ 2023-01-11 17:00:32