ISAP算法
一、为什么我们要学习相比EK、Dinic、SAP算法,时间复杂度更低,可以轻松(不加优化,不卡常)过一些数据强力网络流题,如: [题目传送门](https://www.luogu.org/problemnew/show/P4722)但编程复杂度相差不大,所以在NOIP、NOI、IOI比赛上更具优势,是编写网络流题目的首选
PS:不会Dinic的先去看
二、算法分析
(1)、增广路算法
求解最大流问题的一个比较容易想到的方法就是,每次在残量网络中任意寻找一条从s到t的路径,然后增广,直到不存在这样的路径为止。这就是一般增广路算法。
假设最大流是f那么它的运行时间为O(f⋅∣E∣)但是,这个运行时间并不好,因为它和最大流f有关。
我们发现,如果每次都沿着残量网络中的最短增广路增广,则运行时间可以减为 O(∣E∣2⋅∣V∣) 。这就是最短增广路算法。而 ISAP 算法则是最短增广路算法的一个改进。其实,ISAP 的意思正是「改进的最短增广路」 (Improved Shortest Augmenting Path)。
顺便说一句,上面讨论的所有算法根本上都属于增广路方法。
和它对应的就是大名鼎鼎的预流推进方法。其中最高标号预流推进算法的复杂度可以达到 O(∣V∣2∣E∣−−−√)。
虽然在复杂度上比增广路方法进步很多,但是预流推进算法复杂度的上界是比较紧的,因此有时差距并不会很大。
(2)、允许弧优化
原图存在两种子图,一个是残量网络,一个是允许弧组成的图。残量网络保证可增广,允许弧保证最短路(时间界较优)。
Dinic时间复杂度之所以比较高,是因为它每次进行搜索增广路之前都要进行时间复杂度为O(N)的BFS(每次增广都重新计算dep数组)
PS:dep[MAXN]数组:每个点u到汇点t的最短距离,可以用BFS求出
ISAP对此进行优化,叫做允许弧优化。
然而,ISAP「改进」的地方之一就是,其实没有必要马上更新dep数组。这是因为,去掉一条边只可能令路径变得更长,而如果增广之前的残量网络存在另一条最短路,并且在增广后的残量网络中仍存在,那么这条路径毫无疑问是最短的。所以,ISAP的做法是继续增广,直到遇到死路,才执行回溯操作。
回溯操作的主要任务就是更新dep数组。那么怎么更新呢?非常简单:
1、假设是从节点u找遍了邻接边也没找到允许弧的;
2、再设一变量minn,令minn等于残量网络中u的所有邻接点的dep[v]的最小值,然后令d[u]等于minn+1即可。
这是因为,进入回溯环节说明残量网络中u和t已经不能通过允许弧相连,那么u和t实际上在残量网络中的最短路的长是多少呢?(这正是dep的定义!)
显然是残量网络中u的所有邻接点和t的距离加1的最小情况。特殊情况是,残量网络中u根本没有邻接点。如果是这样,只需要把d[u]设为INF(无限大,一般用2^31-1来代替),这会导致任何点到u的边被排除到残量网络以外。修改之后,只需要把正在dfs的节点u沿着刚才走的路退一步,然后继续搜索即可。
(3) GAP优化
GAP优化可以提前结束程序,很多时候提速非常明显(高达 100 倍以上)。
GAP 优化是说,当发现s,t不连通时,直接结束结束ISAP函数。
怎么发现s,t之间不连通呢,我们已经用dep[MAXN]数组求出每个点到t的最短距离,如果在回溯时发现当前点u是到t点最短距离为dep[u]的最后一个点,即删去这个点后,整个残余网络流图中没有到t点最短距离为dep[u]的点,出现的断层,s到t的最短距离dep[s]一定是所有点中最大的中间没有了一个0<dep[u]<dep[s]的点,便导致s,t不连通。GAP 优化的实现非常简单,用一个数组记录并在适当的时候判断、并及时跳出循环就可以了。
(4)当前弧优化
另一个优化,就是用一个数组保存一个点已经尝试过了哪个邻接边。寻找增广的过程实际上类似于一个BFS过程,因此之前处理过的邻接边是不需要重新处理的(残量网络中的边只会越来越少)。
解决的方法也挺简单的,使用&传地址,及时更新,详见代码
需要注意的一点是,下次应该从上次处理到的邻接边继续处理,而非从上次处理到的邻接边的下一条开始。
三、算法流程
1、定义节点的标号为到汇点的最短距离;
2、每次沿允许弧进行增广;
3、找到增广路后,将路径上所有边的流量更新.
4、遍历完当前结点的可行边后更新当前结点的标号为 dep[u] = min( dp[v] && add_flow(u,v) > 0)+1,使下次再搜的时候有路可走。
5、图中不存在增广路后即退出程序,此时得到的流量值就是最大流。
代码如下:
1 #include2 #define INF 2147483647 3 #define MAXN 20010 4 #define MAXM 400010 5 using namespace std; 6 int n,m,s,t,cnt,maxflow; 7 int head[MAXN],cur[MAXN]; 8 int dep[MAXN],pre[MAXN],num[MAXN]; 9 struct edge{ 10 int nxt,v,w; 11 }e[MAXM]; 12 void add (int u,int v,int w) 13 { 14 e[cnt].v=v; 15 e[cnt].w=w; 16 e[cnt].nxt=head[u]; 17 head[u]=cnt++; 18 } 19 void auto_add (int u,int v,int w) 20 { 21 add (u,v,w);add (v,u,0); 22 } 23 void bfs (int t) 24 { 25 queue q; 26 for (int i=1;i<=n;i++) 27 cur[i]=head[i]; 28 for (int i=1;i<=n;i++) 29 dep[i]=n; 30 dep[t]=0; 31 q.push (t); 32 while (!q.empty()) 33 { 34 int u=q.front(); 35 q.pop(); 36 for (int i=head[u];i!=-1;i=e[i].nxt) 37 if (dep[e[i].v]==n&&e[i^1].w) 38 { 39 dep[e[i].v]=dep[u]+1; 40 q.push (e[i].v); 41 } 42 } 43 } 44 int add_flow (int s,int t) 45 { 46 int ans=INF,u=t; 47 while (u!=s) 48 { 49 ans=min (ans,e[pre[u]].w); 50 u=e[pre[u]^1].v; 51 } 52 u=t; 53 while (u!=s) 54 { 55 e[pre[u]].w-=ans; 56 e[pre[u]^1].w+=ans; 57 u=e[pre[u]^1].v; 58 } 59 return ans; 60 } 61 void ISAP (int s,int t) 62 { 63 int u=s; 64 bfs (t); 65 for (int i=1;i<=n;i++) 66 num[dep[i]]++; 67 while (dep[s]