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;
}
分类: 文章

1 条评论

AIO · 2018年8月10日 11:42 上午

dalao 你的代码在洛谷 RE 了。求修正

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注