ISAP算法，与dinic算法比起来，虽然上界是一样的，但是已经有了很大的进步.
由于ISAP算法是基于dinic算法的优化，所以不会dinic算法的同学可以先看我的另一篇文章：dinic算法.
相对于其他网络流算法，ISAP算法已经十分高效了，而且代码量也较低.而且，很多网络流算法如HLPP，虽然上界比ISAP算法低，但是上界却比较紧，而ISAP算法的上界是很松的，实测中一般比诸如HLPP一类的算法快很多.
所以ISAP其实十分的好用，而且一般网络流都是用ISAP或dinic写的.
ISAP专门针对dinic算法依然存在的缺陷——分层图每次的改变都不大，也就是说每在一张分层图上搜完增广路后，dinic算法会直接用一遍bfs来算出下一张分层图.而这其实没有必要，因为下一张分层图与这张分层图变化不大.
那么怎么从这张分层图推出下一张分层图呢？
我们注意到，分层图的建立全靠一个深度数组deep，也可以说深度就是与源点之间的路径长度.
而ISAP正利用了这个性质，直接在搜到某个点时，无法拓展下去，就直接修改，将当前结点的深度修改掉.
所以整个算法与dinic最大的不同就是：整个算法的deep数组表示的是到剩余网络到汇点的最短路.
所以算法流程如下：
1.做一遍逆向bfs求出初始的deep数组.
2.dfs遍历，当当前结点k无法有剩余的流量却无法继续扩展时，将deep[k]改为deep[最短的扩展节点]+1.
其他过程与dinic基本相同.
首先我们说一下，逆向bfs得益于网络流的成对储存以及逆向边的技巧，可以很快的写出，且不用多存任何东西，具体看代码：
int deep[N+1]={0},q[N+1]={0},h,t,gap[N+1]={0};
void bfs(int start){
memset(deep,0,sizeof(deep));
memset(gap,0,sizeof(gap));
gap[deep[start]=1]=1;
q[h=t=1]=start;
while (h<=t){
for (int i=lin[q[h]];i;i=e[i].next)
if (!deep[e[i].y]){ //零边在dfs中会自动修改的
q[++t]=e[i].y;
deep[e[i].y]=deep[q[h]]+1;
gap[deep[e[i].y]]++; //记录这一层的节点数量
}
++h;
}
}
dfs遍历，顺便把dinic已有的优化和ISAP独特的优化加上，具体细节会写出：
int cur[N+1]={0};
int dfs(int start,int S,int T,int mi){
if (start==T) return mi;
int sum=0,flow;
for (int &i=cur[start];i;i=e[i].next)
if (deep[start]==deep[e[i].y]+1){ //当前弧优化
flow=dfs(e[i].y,S,T,min(mi,e[i].v));
sum+=flow;mi-=flow;
e[i].v-=flow;e[i^1].v+=flow;
if (!mi) return sum; //一个小优化，dinic也有
}
if (!(--gap[deep[start]])) deep[S]=n+1; //断层优化，若中间有一层断开了，就不用更新了
++gap[++deep[start]]; //层数偏移
cur[start]=lin[start]; //更新过层数后，相应的当前弧也得重新初始化
return sum;
}
那么网络流主函数的控制如下：
int maxflow(int S,int T){
int flow;
bfs(T); //将初始的分层图求出
for (int i=1;i<=n;i++)
cur[i]=lin[i]; //当前弧的初始化
flow=dfs(S,S,T,INF); //第一次做遍历
while (deep[S]<=n) flow+=dfs(S,S,T,INF); //不停做遍历直至s到t的最短路径不是简单路径
return flow;
}
网络流的整个算法如下：
int deep[N+1]={0},q[N+1]={0},h,t,gap[N+1]={0};
void bfs(int start){
memset(deep,0,sizeof(deep));
memset(gap,0,sizeof(gap));
gap[deep[start]=1]=1;
q[h=t=1]=start;
while (h<=t){
for (int i=lin[q[h]];i;i=e[i].next)
if (!deep[e[i].y]){
q[++t]=e[i].y;
deep[e[i].y]=deep[q[h]]+1;
gap[deep[e[i].y]]++; //记录这一层的节点数量
}
++h;
}
}
int cur[N+1]={0};
int dfs(int start,int S,int T,int mi){
if (start==T) return mi;
int sum=0,flow;
for (int &i=cur[start];i;i=e[i].next)
if (deep[start]==deep[e[i].y]+1){ //当前弧优化
flow=dfs(e[i].y,S,T,min(mi,e[i].v));
sum+=flow;mi-=flow;
e[i].v-=flow;e[i^1].v+=flow;
if (!mi) return sum; //一个小优化，dinic也有
}
if (!(--gap[deep[start]])) deep[S]=n+1; //断层优化，若中间有一层断开了，就不用更新了
++gap[++deep[start]]; //层数偏移
cur[start]=lin[start]; //更新过层数后，相应的当前弧也得重新初始化
return sum;
}
int maxflow(int S,int T){
int flow;
bfs(T); //将初始的分层图求出
for (int i=1;i<=n;i++)
cur[i]=lin[i]; //当前弧的初始化
flow=dfs(S,S,T,INF); //第一次做遍历
while (deep[S]<=n) flow+=dfs(S,S,T,INF); //不停做遍历直至s到t的最短路径不是简单路径
return flow;
}