题解 P3376 【【模板】网络最大流】

· · 题解

月赛打不下去了，于是来写这题的题解以提高估值

竟然没有 ISAP 的题解？ ISAP 是我大约一年前接触到的，那个时候是自己对照着这个博客自学的，受益匪浅。

有些人可能就会问了既然有 dinic 了，为何还要有 ISAP ？ 因为 ISAP 更快，一般情况下毒瘤出题人也都不太会卡 ISAP 。具体情况可以参考 离散小波变换°巨佬的博客的文末有各大最大流算法的效率对比。因为博客 markdown 崩了，故这里给出原文中的表格

序号 Dinic FF EK 终极 HLPP ISAP
1 0.625s TLE 0.171s 0.125s 0.265s
2 0.562s TLE 0.156s 0.093s 0.265s
3 0.828s TLE 0.625s 0.093s 0.390s
4 0.578s TLE 0.312s 0.093s 0.328s
5 2.468s 24.000s 0.046s 0.078s 0.218s
6 5.546s TLE 0.078s 0.140s 0.203s
7 5.218s 10.984s 0.109s 0.125s 0.328s
8 7.812s 49.953s 0.218s 0.109s 0.265s
9 1.281s TLE 0.375s 0.078s 0.375s
10 0.781s TLE 0.156s 0.062s 0.187s
11 0.312s TLE 0.046s 0.093s 0.203s
12 0.875s TLE 2.703s 0.078s 0.328s
13 0.703s TLE 0.156s 0.156s 0.203s
14 0.500s TLE 0.328s 0.109s 0.218s
15 0.296s TLE 0.171s 0.109s 0.296s
16 0.562s TLE 0.234s 0.125s 0.296s
17 4.687s TLE 0.140s 0.093s 0.343s
18 2.921s TLE 0.031s 0.156s 0.296s
19 2.359s TLE 0.040s 0.078s 0.312s
20 4.656s TLE 0.078s 0.062s 0.390s
21 0.500s TLE 0.312s 0.093s 0.218s
22 1.000s TLE 0.203s 0.109s 0.234s
23 0.343s TLE 0.062s 0.156s 0.265s
24 1.015s TLE 0.281s 0.140s 0.328s
总用时 46.428s - 7.037s 2.553s 6.754s

我们发现除去HLPP，ISAP 吊打全场。

下面就来听我讲解 ISAP 。

\texttt{ISAP(Improved Shortest Augumenting Path)}

在 dinic 中，我们要跑许多遍 bfs ，这就有可能导致算法效率不高。

于是 ISAP 就这样出现了，它只需要跑一遍 bfs !

大体运行过程如下：

·\texttt{1.从t(汇点)到s（源点）跑bfs } ·\texttt{2.从s到t跑dfs} ·\texttt{3.重复操作2直到出现断层}

可能看到这大家都有点懵，心中有许多问号，没关系，下面来介绍原理。

这样我们需要引进 $gap$ 数组， $gap[i]$ 表示高度为 $i$ 的点的个数。显而易见，当 $gap[i]=0$ 时会出现断层，也就是 $s$ 和 $t$ 不再联通，我们也就可以直接退出程序，停止寻找。 下面则是**重点** 我们从终点向起点跑完 $bfs$ 得到最初的高度。但是我们发现，此时还剩下一些流，那么我们将其高度提高，下一次遍历时，就可以把这个流推给其他边。 当然这个算法也可以当前弧优化，因为作者时间关系，后续更新。 先放出裸的 $ISAP$ (这个代码里的注释是我一年前写的，有些繁琐，还请原谅) ```cpp #include<bits/stdc++.h> using namespace std; const int inf=2147483647;//inf:最大值 int cnt=1,head[505];//cnt:第CNT条边head[i]:第i个点属于第几条边 int n,m,s,t;//n个点m条边s:源点t:汇点 inline int Read() { int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; } struct Node { int v;//当前点 int next;//连接点 int val;//容量 }node[100010];//node[i]:第i条边的情况 inline void addedge(int u,int v,int val) { node[++cnt].v=v; node[cnt].val=val; node[cnt].next=head[u]; head[u]=cnt; } int dep[505],gap[505];//dep[i]表示节点i的深度，gap[i]表示深度为i的点的数量 void bfs()//倒着搜 { memset(dep,-1,sizeof(dep));//把深度变为-1(0会导致gap崩坏) memset(gap,0,sizeof(gap)); dep[t]=0;//汇点深度为0 gap[0]=1;//深度为0的点有1个 queue<int>q; q.push(t);//t点入栈 while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 { int v=node[i].v;//v为当前边的下一个点 if(dep[v]!=-1) continue;//dep[v]!=-1相当于v点已被遍历||不管 q.push(v); dep[v]=dep[u]+1;//v点的深度比u点大1 gap[dep[v]]++; }//直到所有点都被遍历过 } return; }//从t到s跑一遍bfs，标记深度 long long maxflow; int dfs(int u,int flow) { if(u==t) { maxflow+=flow; return flow; } int used=0; for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点，就这样遍历下去 { int d=node[i].v; if(node[i].val&&dep[d]+1==dep[u])//如果这条边的残量大于0,且没有断层 { int mi=dfs(d,min(node[i].val,flow-used)); if(mi){ node[i].val-=mi; node[i^1].val+=mi; used+=mi; } if(used==flow)return used; } } //如果已经到了这里，说明该点出去的所有点都已经流过了 //并且从前面点传过来的流量还有剩余 //则此时，要对该点更改dep //使得该点与该点出去的点分隔开 --gap[dep[u]]; if(gap[dep[u]]==0)dep[s]=n+1;//出现断层，无法到达t了 dep[u]++;//层++ gap[dep[u]]++;//层数对应个数++ return used; } long long ISAP() { maxflow=0; bfs(); while(dep[s]<n) dfs(s,inf);//每走一遍增广路,s的层数会加1,如果一直没有出现断层,最多跑n-dep(刚bfs完时s的深度)条增广路共有n个点 return maxflow; } int main() { n=Read(),m=Read(),s=Read(),t=Read(); int u,v,w; for(int i=1;i<=m;i++) { u=Read(); v=Read(); w=Read(); addedge(u,v,w);//正向边 addedge(v,u,0);//反向边 } printf("%lld\n",ISAP()); return 0; } ``` ### update 2020.8.9 $\texttt{ISAP の 当前弧优化} \texttt{Attention:}$ 前文的代码是作者去年写的，后文当前弧优化的代码则是今天写的，故数组定义名称有所区别，并且由结构体存边改为数组存边，还请读者原谅。原先代码中的 $head$ 数组是这个下文的 $h$ 数组 $node[i].v$ 对应 $t[i]......

具体原理和 dinic 一样，随着 dfs 而改变。我们每次找到一条边时，就把当前节点（dfs 中的 u ）对应的 cur 修改为这条边的编号。那么下次遍历到 u 点时，就直接从 cur[u] 开始（也就是说从 h[u] 到 cur[u] 这一段直接不管）。

为什么这一定是正确的呢？

当我们 dfs 时先被遍历的边必然已经增广或无法继续增广，这样的边什么用都没有，除了浪费程序运行时间，故下次再遍历当前节点时，就可以直接跳过没用的点边，这样可以节省一些时间。

↑ 1. 当前弧优化 2. 普通 ISAP

下面放出关键部分代码

int dfs(int u,int flow)
{
    if(u==T)
    {
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int p=cur[u];p;p=nxt[p])
    {
        cur[u]=p;//更新当前弧
        int v=t[p];
        if(val[p]&&dep[v]+1==dep[u])
        {
            int mi=dfs(v,min(flow-used,val[p]));
            if(mi)
            {
                val[p]-=mi;
                val[p^1]+=mi;
                used+=mi;
            }
            if(used==flow)  return used;
        } 
    }
    if(--gap[dep[u]]==0)    dep[s]=n+1;
    dep[u]++;
    gap[dep[u]]++;
    return used;
}
inline long long ISAP()
{
    maxflow=0;
    bfs();
    while(dep[s]<n) memcpy(cur,h,sizeof(h)),dfs(s,INF);
    return maxflow;
}

❀完结撒花❀