其实 ISAP 大部分是不用写 BFS 的。
```cpp
int dfs(int u=s,int ins=INT_MAX)
{
if(u==t) return ins;
int out=0;
F(q,u)
{
if(d[u]>d[v]&&w)
{
int nt=dfs(v,min(w,ins));
ins-=nt;out+=nt;
q.e[j].w-=nt;q.e[j^1].w+=nt;
if(!ins) return out;
}
}
--gap[d[u]];
if(!gap[d[u]]) d[s]=t+1;
++d[u];
++gap[d[u]];
return out;
}
int ISAP()
{
int ans=0;
gap[0]=t;
while(d[s]<t)
memcpy(cur,q.h,sizeof(q.h)),ans+=dfs();
return ans;
}
```
by wxh666 @ 2023-11-03 14:58:56
大概是没加当前弧
by wxh666 @ 2023-11-03 15:05:54
你的 `gap` 优化**如优**
```cpp
int dfs(int now,int flow){
if (now==t) return flow;
int used=0;
for (int i=head[now];i;i=e[i].nxt){
if (e[i].w&&dis[e[i].v]+1==dis[now]){
int f=dfs(e[i].v,min(flow-used,e[i].w));
used+=f;
e[i].w-=f;
e[i^1].w+=f;
if (used==flow) return flow;
}
}
if (!(--gap[dis[now]])) dis[now]=n1*2+n2+n3+1;
dis[now]++;
gap[dis[now]]++;
return used;
}
```
改成
```cpp
int dfs(int now,int flow){
if (now==t) return flow;
int used=0;
for (int i=head[now];i;i=e[i].nxt){
if (e[i].w&&dis[e[i].v]+1==dis[now]){
int f=dfs(e[i].v,min(flow-used,e[i].w));
used+=f;
e[i].w-=f;
e[i^1].w+=f;
if (used==flow) return flow;
}
}
if (!(--gap[dis[now]])) dis[s]=n1*2+n2+n3+1;
dis[now]++;
gap[dis[now]]++;
return used;
}
```
by wxh666 @ 2023-11-03 15:10:19
@[hello_sqt](/user/1032755)
by wxh666 @ 2023-11-03 15:12:39
@[wxh666](/user/342494) 谢谢大佬，猛然发现好多题的gap都写错了
by hello_sqt @ 2023-11-03 15:23:38
@[wxh666](/user/342494) 看懂为啥不用写bfs了，感觉白学isap了
by hello_sqt @ 2023-11-03 15:38:00
@[hello_sqt](/user/1032755) 一般来说不用写 BFS，但是类似卡常时[需要](https://www.luogu.com.cn/discuss/683396)
by wxh666 @ 2023-11-03 15:46:43