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; }