从通用预流推进到先进先出预流推进、HLPP、EXCESS SCALING
a
## 通用预留推进设计
[网络流的定义](https://oi-wiki.org/graph/flow/#%E6%B5%81)
对于一张网络我们需要将初始容量为 $0$ 的反向边也在加入边时进行添加，并依据斜对称性在推送后进行修改，对于剩余容量为$0$的边忽略判断连通性。
然后我们定义进入结点的流超过流出结点的流的剩余部分为超额流，即堵上的。
再后我们定义高度限制流动方向。
那么在推送非超额流后对于超额流我们依据高度向低$1$处推送。
无法推送时，则将其高度提升至最低连通点$+1$。
依次规则直到全部没有超额流。
这是最通用的预留推进算法。
```cpp
#include <iostream>
#include <queue>
using namespace std;
#define int long long
const int inf=1<<30;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int h[1000005],w[1000005],vis[1000005];
queue<int>q;
int relabel(int x)
{
int minn=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
minn=min(minn,h[to]);
}
}
if(minn==inf)
{
return 0;
}
h[x]=minn+1;
return 1;
}
void push_(int x,int i)
{
int flow=min(e[i].val,w[x]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[e[i].to]+=flow;
}
int push_relabel()
{
h[s]=n;
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
if(vis[to]==0&&to!=s&&to!=t&&relabel(to))
{
q.push(to);
vis[to]=1;
}
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(w[x]==0)break;
if(e[i].val==0)continue;
if(h[x]==h[v]+1)
{
push_(x,i);
}
if(w[v]!=0&&v!=s&&v!=t&&vis[v]==0&&relabel(v))
{
q.push(v);
vis[v]=1;
}
}
if(w[x]&&vis[x]==0&&relabel(x))
{
vis[x]=1;
q.push(x);
}
}
return w[t];
}
signed main()
{
int i,j,k;
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
cout<<push_relabel();
return 0;
}
```
[LOJ 良好](https://loj.ac/s/1721019)
[洛谷 良好](https://www.luogu.com.cn/record/104288344)
[UOJ 不好](https://uoj.ac/submission/608381)
但是在大数据下还是远远快于 $\sf Dinic$ 甚至 $\sf ISAP$。
虽然时间复杂度为 $O(n^2m)$ 但实际有时比 $\sf Dinic$ 快得多。
[二分图 洛谷 比较危险](https://www.luogu.com.cn/record/104296784)
## 通用预流推进实际运用尝试
我们寻找一些 Dinic 无法轻易通过的题目测试通用预流推进有多强。
看到 P2057，毫无悬念的通过了。
然后我们看到了 P1361。
只有 $44$ 分，对于最大数据范围需要跑 $60$ 秒。
从建模角度来看，$s$ 到 $t$ 最多四步，预处理了层次就是Dinic 在层数较低时更快的原因。
所以我们也需要预处理层次，不过在预流推进中是高度。
## BFS优化
我们使用 BFS 将 $h_u$ 初始化为 $u$ 到 $t$ 的最短距离。
特殊的 $h_s=n$。
同时也能检查连通性排除无解。
[UOJ 效果不是很显著](https://uoj.ac/submission/611310)
以下的预流推进算法自带此优化不再赘述。
```cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
const int inf=1<<30;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int h[1000005],w[1000005],vis[1000005],cnth[1000005],book[1000005];
queue<int>q;
queue<int>qq;
void bfs()
{
memset(h,0x3f,sizeof(h));
h[t]=0;
qq.push(t);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(e[i^1].val&&h[u]+1<h[v])
{
h[v]=h[u]+1;
if(book[v]==0)
{
qq.push(v);
book[v]=1;
}
}
}
}
}
int relabel(int x)
{
int minn=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
minn=min(minn,h[to]);
}
}
if(minn==inf)
{
return 0;
}
h[x]=minn+1;
return 1;
}
void push_(int x,int i)
{
int flow=min(e[i].val,w[x]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[e[i].to]+=flow;
}
int push_relabel()
{
bfs();
h[s]=n;
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
if(vis[to]==0&&to!=s&&to!=t&&relabel(to))
{
q.push(to);
vis[to]=1;
}
}
}
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(w[x]==0)break;
if(e[i].val==0)continue;
if(h[x]==h[v]+1)push_(x,i);
if(w[v]!=0&&v!=s&&v!=t&&vis[v]==0&&relabel(v))
{
q.push(v);
vis[v]=1;
}
}
if(w[x]&&vis[x]==0&&relabel(x))
{
vis[x]=1;
q.push(x);
}
}
return w[t];
}
signed main()
{
int i,j,k;
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
cout<<push_relabel();
return 0;
}
```
## 先入先出预流推进算法
还是不够快。
你或许认为我们不得不去面对 HPLL了。
但实际上这中间还夹着一个 $O(n^3)$ 的名为 FIFOPP 算法。
非常简单，只需要将上方的通用预流推进算法中的队列改为栈即可跑的飞起。
至于为啥。
自行查看论文。
```cpp
#include <iostream>
#include <queue>
#include <cstring>
#include <stack>
using namespace std;
#define int long long
const int inf=1<<30;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int h[1000005],w[1000005],vis[1000005],cnth[1000005],book[1000005];
stack<int>q;
queue<int>qq;
void bfs()
{
memset(h,0x3f,sizeof(h));
h[t]=0;
qq.push(t);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(e[i^1].val&&h[u]+1<h[v])
{
h[v]=h[u]+1;
if(book[v]==0)
{
q.push(v);
book[v]=1;
}
}
}
}
}
int relabel(int x)
{
int minn=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
minn=min(minn,h[to]);
}
}
if(minn==inf)
{
return 0;
}
h[x]=minn+1;
return 1;
}
void push_(int x,int i)
{
int flow=min(e[i].val,w[x]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[e[i].to]+=flow;
}
int push_relabel()
{
h[s]=n;
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
if(vis[to]==0&&to!=s&&to!=t&&relabel(to))
{
q.push(to);
vis[to]=1;
}
}
}
while(!q.empty())
{
int x=q.top();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(w[x]==0)break;
if(e[i].val==0)continue;
if(h[x]==h[v]+1)push_(x,i);
if(w[v]!=0&&v!=s&&v!=t&&vis[v]==0&&relabel(v))
{
q.push(v);
vis[v]=1;
}
}
if(w[x]&&vis[x]==0&&relabel(x))
{
vis[x]=1;
q.push(x);
}
}
return w[t];
}
signed main()
{
int i,j,k;
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
cout<<push_relabel();
return 0;
}
```
[UOJ 极大的提升](https://uoj.ac/submission/611337)
## 最高标号预流推进算法
这里正式介绍 HLPP 算法。
最高标号预流推进算法，顾名思义用优先队列代替队列每次取超额流最大的点推送。
然后依然是进行通用预流推进。
同时还是带上 BFS优化。
[UOJ 效果十分明显 （HLPP）](https://uoj.ac/submission/611313)
[UOJ 又多过一个点 （HLPP-BFS）](https://uoj.ac/submission/611312)
```cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
const int inf=1<<30;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int h[1000005],w[1000005],vis[1000005],cnth[1000005],book[1000005];
struct cmp
{
inline bool operator ()(int a,int b) const
{
return h[a]<h[b];
}
};
priority_queue<int,vector<int>,cmp>q;
queue<int>qq;
void bfs()
{
memset(h,0x3f,sizeof(h));
h[t]=0;
qq.push(t);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(e[i^1].val&&h[u]+1<h[v])
{
h[v]=h[u]+1;
if(book[v]==0)
{
qq.push(v);
book[v]=1;
}
}
}
}
}
int relabel(int x)
{
int minn=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
minn=min(minn,h[to]);
}
}
if(minn==inf)
{
return 0;
}
h[x]=minn+1;
return 1;
}
void push_(int x,int i)
{
int flow=min(e[i].val,w[x]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[e[i].to]+=flow;
}
int push_relabel()
{
bfs();
h[s]=n;
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
if(vis[to]==0&&to!=s&&to!=t&&relabel(to))
{
q.push(to);
vis[to]=1;
}
}
}
while(!q.empty())
{
int x=q.top();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(w[x]==0)break;
if(e[i].val==0)continue;
if(h[x]==h[v]+1)push_(x,i);
if(w[v]!=0&&v!=s&&v!=t&&vis[v]==0&&relabel(v))
{
q.push(v);
vis[v]=1;
}
}
if(w[x]&&vis[x]==0&&relabel(x))
{
vis[x]=1;
q.push(x);
}
}
return w[t];
}
signed main()
{
int i,j,k;
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
cout<<push_relabel();
return 0;
}
```
虽然快了 $20$ 秒。
可是我们还是无法通过上题。
## GAP 优化 HLPP
$\sf gap \ \ n.$ $缺口$
当不存在 $u$ 使 $h(u)=k$ 那么使 $h(u)>k$ 的 $u$ 的 $h(u)=n+1$
即高度出现缺口，将其迅速推回，节省大量的对高度重定的操作。
同时因为可以迅速推回，所以对每个操作都进行相关的优化，存在大量细节问题，如日报中的HLPP遇到不连通的点会RE。
[UOJ HLPP(BFS+GAP)](https://uoj.ac/submission/611329)
[洛谷 HLPP(BFS+GAP)](https://www.luogu.com.cn/record/104360041)
应该是完美的模板：
```cpp
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
const int inf=1<<30;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
head[x]=cnt;
}
int h[1000005],w[1000005],vis[1000005],cnth[1000005],book[1000005];
struct cmp
{
inline bool operator ()(int a,int b) const
{
return h[a]<h[b];
}
};
priority_queue<int,vector<int>,cmp>q;
queue<int>qq;
void bfs()
{
memset(h,0x3f,sizeof(h));
h[t]=0;
qq.push(t);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(e[i^1].val&&h[u]+1<h[v])
{
h[v]=h[u]+1;
if(book[v]==0)
{
qq.push(v);
book[v]=1;
}
}
}
}
}
void relabel(int x)
{
h[x]=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
h[x]=min(h[x],h[to]+1);
}
}
}
void push_(int x,int i)
{
int flow=min(e[i].val,w[x]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[e[i].to]+=flow;
}
int push_relabel()
{
bfs();
if(h[s]==0x3f3f3f)return 0;
h[s]=n;
for(int i=1;i<=n;i++)
{
if(h[i]<0x3f3f3f)
{
cnth[h[i]]++;
}
}
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
if(vis[to]==0&&to!=s&&to!=t)
{
q.push(to);
vis[to]=1;
}
}
}
while(!q.empty())
{
int x=q.top();
q.pop();
vis[x]=0;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(e[i].val&&h[x]==h[v]+1)
{
push_(x,i);
if(v!=s&&v!=t&&vis[v]==0)
{
q.push(v);
vis[v]=1;
}
}
if(w[x]==0)i=0;
}
if(w[x]&&h[x]<=n+1)
{
cnth[h[x]]--;
if(cnth[h[x]]==0)
{
for(int i=1;i<=n;i++)
{
if(h[i]>h[x]&&i!=s&&i!=t&&h[i]<n+1)
{
h[i]=n+1;
}
}
}
relabel(x);
cnth[h[x]]++;
vis[x]=1;
q.push(x);
}
}
return w[t];
}
signed main()
{
int i,j,k;
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,0);
}
cout<<push_relabel();
return 0;
}
```
值得注意的是带 GAP 优化的 HLPP 会遍历点，所以在建模后更改 $n$ 的数值，其余则不需要。
[成功的通过了上题](https://www.luogu.com.cn/record/104364741)
## GAP 优化其它
对于通用预流推进优先队列改回队列即可
[洛谷 有用但不多](https://www.luogu.com.cn/record/104379703)
[UOJ 有用但不多](https://uoj.ac/submission/611349)
对于 FIFOPP
将上代码中的优先队列改为栈即可。
常数会更优一些，因此具有使用价值
[UOJ 只慢一点](https://uoj.ac/submission/611340)
[洛谷 它甚至更快一些](https://www.luogu.com.cn/record/104375311)
## 节点选择改进尝试
对于通用的预流推进算法。
队列存储溢出节点并不是必须的。
可以发现以上两种改进均是对溢出节点的挑选方式进行的调整。
那我们试试挑选超额流最大的节点推进。
[UOJ 只慢一点](https://uoj.ac/submission/611510)
[洛谷 未能通过](https://www.luogu.com.cn/record/104482582)
我们也可以将优先队列的排列方式改为按照 $e_i+h_i$ 。
[UOJ 还是慢一点](https://uoj.ac/submission/611512)
所以各种存储排列方式预流推进实质上是对选择点的改进。
## EXCESS SCALING
[论文](https://www.cs.princeton.edu/courses/archive/fall07/cos521/handouts/0.pdf)
----
我的理解：
我们进行 $\log U$ 次 Scaling，每次不断选择 $\Delta/2\leq e_i$ 中 $h_i$ 最小的进行推一次流，更新当前弧，推不了重贴，重置当前弧，保证推到的点的超额流之后仍 $<\Delta$，直到没有 $\Delta/2\leq e_i$，然后 $\Delta$ 减半进入下一轮。
----
来自CHAT-GPT：
EXCESS SCALING 算法的流程如下：
预流推进初始化：将源点 $s$ 的所有边设定为满载流量，源点 $s$ 的 $h$ 值设定为节点数 $n$，汇点 $t$ 的 $h$ 值为 $0$。同时将 $s$ 的所有出边加入到高度为 $1$ 的桶中。
excess flow scaling：每次推进时限定每条边所能流入的流量为 $f \le 2^k$，其中 $k$ 是一个不断减小的指数。初始值为 $k = \lfloor \log C \rfloor$，其中 $C$ 是图中边权的最大值。当 $k < 0$ 时，停止算法。
桶排操作：按照节点的高度 $h$，将所有节点放入相应的高度桶中。同时建立超额流桶，将超额流的节点放入其中。
推进流：从高度最大的桶开始，取出其中的节点 $u$。如果节点 $u$ 的超额流 $e_u$ 大于 $0$，则将其推进至相邻节点 $v$。如果 $v$ 的高度 $h_v < h_u$，则 $u$ 将超额流 $e_u$ 推进至 $v$，更新 $e_u$ 和 $e_v$。如果 $v$ 的超额流 $e_v$ 大于 $0$，则将其加入超额流桶中。
重贴标签：如果 $u$ 的超额流 $e_u$ 发生变化，使其超额流不为 $0$，则将其高度 $h_u$ 置为最小的与其相邻的节点的高度加 $1$。
当高度为 $h_s > n$ 时，停止算法。此时，$t$ 的超额流大小即为最大流。
在 EXCESS SCALING 算法中，$k$ 的初始值是 $\lfloor \log_2 C \rfloor$，其中 $C$ 是图中边的最大容量。每次执行 excess flow scaling 阶段时，$k$ 的值会减小，一般是 $k \leftarrow \lfloor k/2 \rfloor$，直到 $k=0$。这样做的原因是随着算法的进行，残量网络中的流量会逐渐减小，因此可以逐步减小 $k$ 的值，以加快算法的收敛速度。
----
```cpp
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
inline int read()
{
int x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x;
}
int K,level;
const int inf=(long long)1<<40;
int n,m,s,t;
struct edge
{
int to,val,next;
}e[1000005];
int cnt=1,head[1000005],now[1000005];
void add(int x,int y,int z)
{
cnt++;
e[cnt].to=y;
e[cnt].val=z;
e[cnt].next=head[x];
now[x]=head[x]=cnt;
}
int h[12005],w[12005],cnth[12005];
queue<int>list[12005];
queue<int>qq;
int book[12005];
void bfs()
{
memset(h,0x3f,sizeof(h));
h[t]=0;
qq.push(t);
while(!qq.empty())
{
int u=qq.front();
qq.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(e[i^1].val&&h[u]+1<h[v])
{
h[v]=h[u]+1;
if(book[v]==0)
{
qq.push(v);
book[v]=1;
}
}
}
}
}
void push_relabel(int x,int Delta)
{
int i;
int found=0;
for(i=now[x];i;i=e[i].next)
{
int v=e[i].to;
if(h[x]==h[v]+1&&e[i].val)
{
found=1;
break;
}
else
{
now[x]=e[i].next;
}
}
if(found==1)
{
int v=e[i].to;
int flow=min(e[i].val,w[x]);
if(v!=t)flow=min(e[i].val,Delta-w[v]);
e[i].val-=flow;
e[i^1].val+=flow;
w[x]-=flow;
w[v]+=flow;
if(w[x]<=Delta/2)list[h[x]].pop();
if(w[v]>Delta/2&&v!=s&&v!=t)
{
list[h[v]].push(v);
level--;
}
}
else
{
list[h[x]].pop();
cnth[h[x]]--;
if(cnth[h[x]]==0)
{
for(int i=1;i<=n;i++)
{
if(h[i]>h[x]&&i!=s&&i!=t&&h[i]<n+1)
{
h[i]=n+1;
}
}
}
int minn=inf;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(e[i].val)
{
minn=min(minn,h[to]);
}
}
h[x]=minn+1;
if(minn==inf)h[x]=n+1;
cnth[h[x]]++;
list[h[x]].push(x);
now[x]=head[x];
}
}
int Excess_Scaling()
{
bfs();
if(h[s]==0x3f3f3f)return 0;
h[s]=n;
for(int i=1;i<=n;i++)
{
if(h[i]<0x3f3f3f)
{
cnth[h[i]]++;
}
}
for(int i=head[s];i;i=e[i].next)
{
int to=e[i].to,val=e[i].val;
if(val)
{
e[i].val-=val;
e[i^1].val+=val;
w[s]-=val;
w[to]+=val;
}
}
for(int k=1;k<=K;k++)
{
int Delta=(long long)1<<(K-k);
for(int i=1;i<=n;i++)
{
if(w[i]>Delta/2)
{
list[h[i]].push(i);
}
}
level=1;
while(level<=n)
{
if(list[level].empty())level++;
else
{
int x=list[level].front();
push_relabel(x,Delta);
}
}
for(int i=1;i<=32;i++)
{
while(!list[i].empty())
{
list[i].pop();
}
}
}
return w[t];
}
signed main()
{
int i,j,k;
n=read();
m=read();
s=read();
t=read();
for(i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
K=max(K,(int)log2(z-1)+1);
add(x,y,z);
add(y,x,0);
}
K++;
cout<<Excess_Scaling();
return 0;
}
```
