题解 P3376 【【模板】网络最大流】
_Fontainebleau_
·
·
题解
月赛打不下去了，于是来写这题的题解以提高估值
竟然没有 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;
}
❀完结撒花❀