a

## 通用預(yù)留推進(jìn)設(shè)計(jì)?

[網(wǎng)絡(luò)流的定義](https://oi-wiki.org/graph/flow/#%E6%B5%81)

對(duì)于一張網(wǎng)絡(luò)我們需要將初始容量為 $0$ 的反向邊也在加入邊時(shí)進(jìn)行添加，并依據(jù)斜對(duì)稱(chēng)性在推送后進(jìn)行修改，對(duì)于剩余容量為$0$的邊忽略判斷連通性。

然后我們定義進(jìn)入結(jié)點(diǎn)的流超過(guò)流出結(jié)點(diǎn)的流的剩余部分為超額流，即堵上的。

再后我們定義高度限制流動(dòng)方向。

那么在推送非超額流后對(duì)于超額流我們依據(jù)高度向低$1$處推送。

無(wú)法推送時(shí)，則將其高度提升至最低連通點(diǎn)$+1$。

依次規(guī)則直到全部沒(méi)有超額流。

這是最通用的預(yù)留推進(jìn)算法。

```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)

但是在大數(shù)據(jù)下還是遠(yuǎn)遠(yuǎn)快于 $\sf Dinic$ 甚至 $\sf ISAP$。

雖然時(shí)間復(fù)雜度為 $O(n^2m)$ 但實(shí)際有時(shí)比 $\sf Dinic$ 快得多。

[二分圖 洛谷 比較危險(xiǎn)](https://www.luogu.com.cn/record/104296784)

## 通用預(yù)流推進(jìn)實(shí)際運(yùn)用嘗試

我們尋找一些 Dinic 無(wú)法輕易通過(guò)的題目測(cè)試通用預(yù)流推進(jìn)有多強(qiáng)。

看到 P2057，毫無(wú)懸念的通過(guò)了。

然后我們看到了 P1361。

只有 $44$ 分，對(duì)于最大數(shù)據(jù)范圍需要跑 $60$ 秒。

從建模角度來(lái)看，$s$ 到 $t$ 最多四步，預(yù)處理了層次就是Dinic 在層數(shù)較低時(shí)更快的原因。

所以我們也需要預(yù)處理層次，不過(guò)在預(yù)流推進(jìn)中是高度。

## BFS優(yōu)化

我們使用 BFS 將 $h_u$ 初始化為 $u$ 到 $t$ 的最短距離。

特殊的 $h_s=n$。

同時(shí)也能檢查連通性排除無(wú)解。

[UOJ 效果不是很顯著](https://uoj.ac/submission/611310)

以下的預(yù)流推進(jìn)算法自帶此優(yōu)化不再贅述。

```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;

}

```

## 先入先出預(yù)流推進(jìn)算法

還是不夠快。

你或許認(rèn)為我們不得不去面對(duì) HPLL了。

但實(shí)際上這中間還夾著一個(gè) $O(n^3)$ 的名為 FIFOPP 算法。

非常簡(jiǎn)單，只需要將上方的通用預(yù)流推進(jìn)算法中的隊(duì)列改為棧即可跑的飛起。

至于為啥。

自行查看論文。

```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)

## 最高標(biāo)號(hào)預(yù)流推進(jìn)算法

這里正式介紹 HLPP 算法。

最高標(biāo)號(hào)預(yù)流推進(jìn)算法，顧名思義用優(yōu)先隊(duì)列代替隊(duì)列每次取超額流最大的點(diǎn)推送。

然后依然是進(jìn)行通用預(yù)流推進(jìn)。

同時(shí)還是帶上 BFS優(yōu)化。

[UOJ 效果十分明顯 （HLPP）](https://uoj.ac/submission/611313)

[UOJ 又多過(guò)一個(gè)點(diǎn) （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$ 秒。

可是我們還是無(wú)法通過(guò)上題。

## GAP 優(yōu)化 HLPP

$\sf gap \ \? n.$ $缺口$

當(dāng)不存在 $u$ 使 $h(u)=k$ 那么使 $h(u)>k$ 的 $u$ 的 $h(u)=n+1$

即高度出現(xiàn)缺口，將其迅速推回，節(jié)省大量的對(duì)高度重定的操作。

同時(shí)因?yàn)榭梢匝杆偻苹?，所以?duì)每個(gè)操作都進(jìn)行相關(guān)的優(yōu)化，存在大量細(xì)節(jié)問(wèn)題，如日?qǐng)?bào)中的HLPP遇到不連通的點(diǎn)會(huì)RE。

[UOJ HLPP(BFS+GAP)](https://uoj.ac/submission/611329)

[洛谷 HLPP(BFS+GAP)](https://www.luogu.com.cn/record/104360041)

應(yīng)該是完美的模板：

```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 優(yōu)化的 HLPP 會(huì)遍歷點(diǎn)，所以在建模后更改 $n$ 的數(shù)值，其余則不需要。

[成功的通過(guò)了上題](https://www.luogu.com.cn/record/104364741)

## GAP 優(yōu)化其它

對(duì)于通用預(yù)流推進(jìn)優(yōu)先隊(duì)列改回隊(duì)列即可

[洛谷 有用但不多](https://www.luogu.com.cn/record/104379703)

[UOJ 有用但不多](https://uoj.ac/submission/611349)

對(duì)于 FIFOPP

將上代碼中的優(yōu)先隊(duì)列改為棧即可。

常數(shù)會(huì)更優(yōu)一些，因此具有使用價(jià)值

[UOJ 只慢一點(diǎn)](https://uoj.ac/submission/611340)

[洛谷 它甚至更快一些](https://www.luogu.com.cn/record/104375311)

## 節(jié)點(diǎn)選擇改進(jìn)嘗試

對(duì)于通用的預(yù)流推進(jìn)算法。

隊(duì)列存儲(chǔ)溢出節(jié)點(diǎn)并不是必須的。

可以發(fā)現(xiàn)以上兩種改進(jìn)均是對(duì)溢出節(jié)點(diǎn)的挑選方式進(jìn)行的調(diào)整。

那我們?cè)囋囂暨x超額流最大的節(jié)點(diǎn)推進(jìn)。

[UOJ 只慢一點(diǎn)](https://uoj.ac/submission/611510)

[洛谷 未能通過(guò)](https://www.luogu.com.cn/record/104482582)

我們也可以將優(yōu)先隊(duì)列的排列方式改為按照 $e_i+h_i$ 。

[UOJ 還是慢一點(diǎn)](https://uoj.ac/submission/611512)

所以各種存儲(chǔ)排列方式預(yù)流推進(jìn)實(shí)質(zhì)上是對(duì)選擇點(diǎn)的改進(jìn)。

## EXCESS SCALING

[論文](https://www.cs.princeton.edu/courses/archive/fall07/cos521/handouts/0.pdf)


----

我的理解：

我們進(jìn)行 $\log U$ 次 Scaling，每次不斷選擇 $\Delta/2\leq e_i$ 中 $h_i$ 最小的進(jìn)行推一次流，更新當(dāng)前弧，推不了重貼，重置當(dāng)前弧，保證推到的點(diǎn)的超額流之后仍 $<\Delta$，直到?jīng)]有 $\Delta/2\leq e_i$，然后 $\Delta$ 減半進(jìn)入下一輪。

----

來(lái)自CHAT-GPT：

EXCESS SCALING 算法的流程如下：

預(yù)流推進(jìn)初始化：將源點(diǎn) $s$ 的所有邊設(shè)定為滿載流量，源點(diǎn) $s$ 的 $h$ 值設(shè)定為節(jié)點(diǎn)數(shù) $n$，匯點(diǎn) $t$ 的 $h$ 值為 $0$。同時(shí)將 $s$ 的所有出邊加入到高度為 $1$ 的桶中。

excess flow scaling：每次推進(jìn)時(shí)限定每條邊所能流入的流量為 $f \le 2^k$，其中 $k$ 是一個(gè)不斷減小的指數(shù)。初始值為 $k = \lfloor \log C \rfloor$，其中 $C$ 是圖中邊權(quán)的最大值。當(dāng) $k < 0$ 時(shí)，停止算法。

桶排操作：按照節(jié)點(diǎn)的高度 $h$，將所有節(jié)點(diǎn)放入相應(yīng)的高度桶中。同時(shí)建立超額流桶，將超額流的節(jié)點(diǎn)放入其中。

推進(jìn)流：從高度最大的桶開(kāi)始，取出其中的節(jié)點(diǎn) $u$。如果節(jié)點(diǎn) $u$ 的超額流 $e_u$ 大于 $0$，則將其推進(jìn)至相鄰節(jié)點(diǎn) $v$。如果 $v$ 的高度 $h_v < h_u$，則 $u$ 將超額流 $e_u$ 推進(jìn)至 $v$，更新 $e_u$ 和 $e_v$。如果 $v$ 的超額流 $e_v$ 大于 $0$，則將其加入超額流桶中。

重貼標(biāo)簽：如果 $u$ 的超額流 $e_u$ 發(fā)生變化，使其超額流不為 $0$，則將其高度 $h_u$ 置為最小的與其相鄰的節(jié)點(diǎn)的高度加 $1$。

當(dāng)高度為 $h_s > n$ 時(shí)，停止算法。此時(shí)，$t$ 的超額流大小即為最大流。

在 EXCESS SCALING 算法中，$k$ 的初始值是 $\lfloor \log_2 C \rfloor$，其中 $C$ 是圖中邊的最大容量。每次執(zhí)行 excess flow scaling 階段時(shí)，$k$ 的值會(huì)減小，一般是 $k \leftarrow \lfloor k/2 \rfloor$，直到 $k=0$。這樣做的原因是隨著算法的進(jìn)行，殘量網(wǎng)絡(luò)中的流量會(huì)逐漸減小，因此可以逐步減小 $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;

}

```