ISAP算法——对dinic算法的进一步优化

时间:2021-12-22 17:58:56

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