ISAP 算法

一、为什么我们要学习

相比 EK、Dinic、SAP 算法，时间复杂度更低，可以轻松（不加优化，不卡常）过一些数据强力网络流题，如：题目传送门

但编程复杂度相差不大，所以在 NOIP、NOI、IOI 比赛上更具优势，是编写网络流题目的首选

PS：不会 Dinic 的先去看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、图中不存在增广路后即退出程序，此时得到的流量值就是最大流。

代码如下：

#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 20010
#define MAXM 400010
using namespace std;
int n,m,s,t,cnt,maxflow;
int head[MAXN],cur[MAXN];
int dep[MAXN],pre[MAXN],num[MAXN];
struct edge{
    int nxt,v,w;
}e[MAXM];
void add (int u,int v,int w)
{
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
void auto_add (int u,int v,int w)
{
    add (u,v,w);add (v,u,0);
}
void bfs (int t)
{
    queue<int>q;
    for (int i=1;i<=n;i++)
        cur[i]=head[i];
    for (int i=1;i<=n;i++)
        dep[i]=n;
    dep[t]=0;
    q.push (t);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=head[u];i!=-1;i=e[i].nxt)
            if (dep[e[i].v]==n&&e[i^1].w)
            {
                dep[e[i].v]=dep[u]+1;
                q.push (e[i].v);
            }
    }
}
int add_flow (int s,int t)
{
    int ans=INF,u=t;
    while (u!=s)
    {
        ans=min (ans,e[pre[u]].w);
        u=e[pre[u]^1].v;
    }
    u=t;
    while (u!=s)
    {
        e[pre[u]].w-=ans;
        e[pre[u]^1].w+=ans;
        u=e[pre[u]^1].v;
    }
    return ans;
}
void ISAP (int s,int t)
{
    int u=s;
    bfs (t);
    for (int i=1;i<=n;i++)
        num[dep[i]]++;
    while (dep[s]<n)
    {
        if (u==t)
            maxflow+=add_flow (s,t),u=s;
        bool flag=0;
        for (int &i=cur[u];i!=-1;i=e[i].nxt)
            if (dep[u]==dep[e[i].v]+1&&e[i].w)
            {
                flag=1;
                u=e[i].v;
                pre[e[i].v]=i;
                break;
            }
        if (!flag)
        {
            int minn=n-1;
            for (int i=head[u];i!=-1;i=e[i].nxt)
                if (e[i].w)
                    minn=min (minn,dep[e[i].v]);
            if ((--num[dep[u]])==0) break;
            num[dep[u]=minn+1]++;
            cur[u]=head[u];
            if (u!=s)
                u=e[pre[u]^1].v;
        }
    }
}
int main()
{
    memset (head,-1,sizeof (head));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        auto_add (u,v,w);
    }
    ISAP (s,t);
    printf ("%d",maxflow);
    return 0;
}