题解 P4722 【【模板】最大流 加强版 / 预流推进】
KevinYu
2018-12-07 20:55:00
------------
## ------------前言------------
------------
这一题来发一个题解，来介绍两个重点:较慢的HLPP的写法(也是经典写法，实现起来简单)，以及那些最优解们对原做法的优化。
------------
## ------------Part1.HLPP经典写法:------------
------------
我参照第一篇题解的方法写出来的代码勉强能趁着luogu一个评测机波动卡过去，在[P3376](https://www.luogu.org/problemnew/show/P3376)网络最大流的原题上倒是跑得飞快。
那么，我们先来看看经典写法的原理。
HLPP，全称Highest Label Preflow Push，最高标号预流推进算法。与常见的网络流算法（FF，EK，Dinic，ISAP）不同，它是一个预流推进算法，并不依赖增广路实现。
**注意:虽然这个算法的原理与常见网络流算法的不同，但理解常用的网络流算法的思想会对理解这个算法有帮助，后面我会进行一些比喻来帮助你们加深对这个算法。**
(我也会尽力让不懂其他几个算法的原理的同学们理解的)
与人类的人脑模拟一个网络流的过程相同，它通过将每一个点的流量"发送"给下一个点来模拟流动。
例:(假设下图是从1到4)
注意图中的黄框和绿框标识的部分:
黄框中的流量总是不变的(即**网络源**能**无限制**的推送流量)。
在最后一次的推送中，我们的2号节点将其推送不出的流量"返还"给了网络源，而最后一个点的流量并未返还（即**网络汇**的流量**不会回流**），且**当所有的推送过程结束后**，**汇点**存储的流量就是网络最大流。
信息量有点大，建议喝口茶休息一下，好好的琢磨一下原理~~，免得头发掉光了~~。
在了解预流推进算法的原理后，我们就可以试着去了解HLPP了。
不过，在介绍HLPP之前，我们要先了解几个概念:
1.**超额流**:我们将存储在**源点外**的节点中的流量称为超额流。
2.**推送**:一个节点将其存储的**超额流**传递给**与其直接相邻**的节点的过程被称为"推送"。
3.**节点高度**:我们发现我们先前设计的推进算法有一点**缺陷**:我们的节点可能会"打太极"(你推送给我，我再推送给你，一直推送到TLE)。为了防止这种丧尽天良的事情发生，我们给**每一个节点**加上**高度**，并规定推进**只能**从高点到低点进行。
4.**重贴标签**:万一我们的**节点**"四面楚歌"，**处在**一堆节点中的**最低谷**，却又**携带着**贵重的**超额流**，我们又该如何化解僵局呢?我们在这时就要抬高这个节点的高度，让其能流向下一个节点了，**抬高**这个**节点**的**高度**的过程，被我们称作"重贴标签"。
有了这几个概念，我们就可以将HLPP分为四个部分了:
1.bfs预处理节点高度(此处类似Dinic的分层bfs)。
2.push操作进行推进(此处类似求增广路径，不过这里的推进是以层为单位的，而增广是以路径为单位的)。
3.relabel重贴标签改变节点高度(此处类似ISAP对增广路径上节点的层数的修改操作)。
4.HLPP主过程求最大流。
<强调>
出现在这里的内容在后面逐步分析算法时还会出现(因为实在是太重要了)。
1.HLPP的bfs与Dinic的极其类似，但却是**反向的**，切记不能混淆。
2.push操作与增广路径的侧重点不同，更侧重于**当前点的流量修改**(一次push操作会尽量地清空点的超额流)。
3.relabel操作与ISAP的偏移层数有不同之处，它一次可以抬高**不止一个单位高度**，且一般抬到其中的流量**恰好能**流向下一个节点。
</强调>
我们来分步看看这个算法是怎么实现的。
1.bfs分层。
这个部分相对简单，但要注意我们是从汇点开始搜的，并且它是一个bool函数，用来判断是否存在从源到汇的可行流。
这里规定```h[i]```为节点i的高度。
初始化:
在这一步中我们将**每一个节点的高度抬高到INF**(高度为INF的节点不在网络中)，并将终点入队:
```cpp
il bool bfs()
{
re int i;
memset(h+1,inf,sizeof(int)*n);
h[ed]=0;
q.push(ed);
```
接着，我们依次地取出队内元素:
```cpp
while(!q.empty())
{
int t=q.front();
q.pop();
for(i=head[t];i!=-1;i=a[i].next)
{
int v=a[i].to;
```
更新每一个在网络内的节点的高度:
注意了，这里是**反向搜索**，所以判断一条边是否为可行流，要判断与**其成对建立的反边**。
```cpp
if(a[i^1].flow&&h[v]>h[t]+1)
{
h[v]=h[t]+1;
q.push(v);
}
}
}
return h[st]!=inf;
}
```
bfs过程完整代码:
```cpp
il bool bfs()
{
re int i;
memset(h+1,inf,sizeof(int)*n);
h[ed]=0;
q.push(ed);
while(!q.empty())
{
int t=q.front();
q.pop();
for(i=head[t];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(a[i^1].flow&&h[v]>h[t]+1)
{
h[v]=h[t]+1;
q.push(v);
}
}
}
return h[st]!=inf;
}
```
接下来是push操作。
由于**不是求一条路径**，仅仅是取一个点和比它低的邻点，我们只需要遍历当前点的邻点:
```cpp
il void push(int u)
{
re int i;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
```
在这之后，我们找到每一个在网络内的比它低的节点,并将它的超额流传递给下一位。
pq是一个以节点高度为关键字的优先队列:
```cpp
struct cmp
{
il bool operator ()(int xi,int yi)const
{
return h[xi]<h[yi];
}
};
priority_queue<int,vector<int>,cmp> pq;
```
而```e[i]```存储的是i号节点的超额流。
```cpp
if((a[i].flow)&&(h[v]+1==h[u]))
{
int df=min(e[u],a[i].flow);
a[i].flow-=df;
a[i^1].flow+=df;
e[u]-=df;
e[v]+=df;
if((v!=st)&&(v!=ed)&&(!vis[v]))
{
pq.push(v);
vis[v]=1;
}
if(!e[u])break;
}
}
}
```
要注意在这里，我们只将除起点与终点外的点送入优先队列。
push过程完整代码:
```cpp
il void push(int u)
{
re int i;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if((a[i].flow)&&(h[v]+1==h[u]))
{
int df=min(e[u],a[i].flow);
a[i].flow-=df;
a[i^1].flow+=df;
e[u]-=df;
e[v]+=df;
if((v!=st)&&(v!=ed)&&(!vis[v]))
{
pq.push(v);
vis[v]=1;
}
if(!e[u])break;
}
}
}
```
紧接着push的，是与它孪生的relabel操作。
其实很简单，就是将一个节点的高度抬高到**恰好能**流向下一个节点。
relabel操作代码:
```cpp
il void relabel(int u)
{
re int i;
h[u]=inf;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if((a[i].flow)&&(h[v]+1<h[u]))h[u]=h[v]+1;
}
}
```
有了这几个操作做基础，我们就可以尝试用预流推进的思想求解最大流了。
接下来我们要实现的是HLPP的主函数，比起其他的最大流算法，它的主函数更为复杂。
过一遍算法流程:
1.初始化:
这里有一个数组:gap数组。
与Dinic里的gap优化类似，HLPP里的```gap[i]```记录每一个高度有多少的点。
```cpp
inline int hlpp()
{
re int i;
if(!bfs())return 0;
h[st]=n;
memset(gap,0,sizeof(int)*(n<<1));
for(i=1;i<=n;i++)if(h[i]!=inf)gap[h[i]]++;
```
1.由于我们的网络源的流量是无限的，为了避免一条边的的流量是INT_MAX这种开玩笑的数字，导致网络源直接将其容量流干(就是INF开小的问题)，我们将源点发出的边单独拿出来进行推流。
```cpp
for(i=head[st];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(int f=a[i].flow)
{
a[i].flow-=f;a[i^1].flow+=f;
e[st]-=f;e[v]+=f;
if(v!=st&&v!=ed&&!vis[v])
{
pq.push(v);
vis[v]=1;
}
}
}
```
你可能会问:为什么不直接开long long呢？这样码量会小很多啊？
主要还是还是效率问题，long long太慢了。
2.我们将当前最高的点从优先队列中取出，并判断是否有超额流:
```cpp
while(!pq.empty())
{
int t=pq.top();pq.pop();
vis[t]=0;push(t);
if(e[t])
{
```
3.这里的gap优化就要起作用了，若最高点所处的层数只有它一个，我们就将其高度改为n+1层:
```cpp
gap[h[t]]--;
if(!gap[h[t]])
{
for(re int v=1;v<=n;v++)
{
if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]<n+1)
{
h[v]=n+1;
}
}
}
```
这样它的超额流就可以直接流回源点。
4.接下来就将它的标签重贴，并进行推流:
```cpp
relabel(t);gap[h[t]]++;
pq.push(t);vis[t]=1;
}
}
```
5.最后返回汇点的超额流,算法结束:
```cpp
return e[ed];
}
```
HLPP主过程完整代码:
```cpp
inline int hlpp()
{
re int i;
if(!bfs())return 0;
h[st]=n;
memset(gap,0,sizeof(int)*(n<<1));
for(i=1;i<=n;i++)if(h[i]!=inf)gap[h[i]]++;
for(i=head[st];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(int f=a[i].flow)
{
a[i].flow-=f;a[i^1].flow+=f;
e[st]-=f;e[v]+=f;
if(v!=st&&v!=ed&&!vis[v])
{
pq.push(v);
vis[v]=1;
}
}
}
while(!pq.empty())
{
int t=pq.top();pq.pop();
vis[t]=0;push(t);
if(e[t])
{
gap[h[t]]--;
if(!gap[h[t]])
{
for(re int v=1;v<=n;v++)
{
if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]<n+1)
{
h[v]=n+1;
}
}
}
relabel(t);gap[h[t]]++;
pq.push(t);vis[t]=1;
}
}
return e[ed];
}
```
HLPP(经典写法)完整代码:
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF (1ll<<49ll)+1ll
#define inf 0x3f3f3f3f
#define re register
#define il inline
using namespace std;
struct edge
{
int to,next;
int flow;
}a[2000020];
int head[10010];
int gap[10010];
int h[10010];
int e[10010];
int vis[10010];
int cnt(0);
int n,m,st,ed;
struct cmp
{
il bool operator ()(int xi,int yi)const
{
return h[xi]<h[yi];
}
};
priority_queue<int,vector<int>,cmp> pq;
queue<int> q;
il void addedge(int xi,int yi,int fi)
{
a[cnt].to=yi;
a[cnt].next=head[xi];
a[cnt].flow=fi;
head[xi]=cnt++;
}
il bool bfs()
{
re int i;
memset(h+1,inf,sizeof(int)*n);
h[ed]=0;
q.push(ed);
while(!q.empty())
{
int t=q.front();
q.pop();
for(i=head[t];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(a[i^1].flow&&h[v]>h[t]+1)
{
h[v]=h[t]+1;
q.push(v);
}
}
}
return h[st]!=inf;
}
il void push(int u)
{
re int i;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if((a[i].flow)&&(h[v]+1==h[u]))
{
int df=min(e[u],a[i].flow);
a[i].flow-=df;
a[i^1].flow+=df;
e[u]-=df;
e[v]+=df;
if((v!=st)&&(v!=ed)&&(!vis[v]))
{
pq.push(v);
vis[v]=1;
}
if(!e[u])break;
}
}
}
il void relabel(int u)
{
re int i;
h[u]=inf;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;
if((a[i].flow)&&(h[v]+1<h[u]))h[u]=h[v]+1;
}
}
inline int hlpp()
{
re int i;
if(!bfs())return 0;
h[st]=n;
memset(gap,0,sizeof(int)*(n<<1));
for(i=1;i<=n;i++)if(h[i]!=inf)gap[h[i]]++;
for(i=head[st];i!=-1;i=a[i].next)
{
int v=a[i].to;
if(int f=a[i].flow)
{
a[i].flow-=f;a[i^1].flow+=f;
e[st]-=f;e[v]+=f;
if(v!=st&&v!=ed&&!vis[v])
{
pq.push(v);
vis[v]=1;
}
}
}
while(!pq.empty())
{
int t=pq.top();pq.pop();
vis[t]=0;push(t);
if(e[t])
{
gap[h[t]]--;
if(!gap[h[t]])
{
for(re int v=1;v<=n;v++)
{
if(v!=st&&v!=ed&&h[v]>h[t]&&h[v]<n+1)
{
h[v]=n+1;
}
}
}
relabel(t);gap[h[t]]++;
pq.push(t);vis[t]=1;
}
}
return e[ed];
}
signed main()
{
re int i;
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&st,&ed);
for(i=1;i<=m;i++)
{
int x,y;
ll f;
scanf("%d%d%lld",&x,&y,&f);
addedge(x,y,f);
addedge(y,x,0);
}
ll maxf=hlpp();
printf("%lld",maxf);
return 0;
}
```
------------
## ------------Part1结束------------
------------
## ------------Part2.最优解的优化------------
------------
Part2并不是这篇题解的重点，也不是学习HLPP必须了解的内容，仅仅是向大家介绍最优解所做的优化而已。
因为最优解实在有些复杂，而博主所说毕竟只是一家之言，无法代表广大OIer们的观点，你们也可以选择看他们的代码自己参透他们的做法。
虽说**Part1介绍的方法**已经足够应付**大多数**情况了，但是要过这道题用前面的代码**即使开了O2**还是十分的勉强。
然而那些最优解一个个跑得飞快。(加入公开计划的话就可以查看他们的代码了，建议加入，可以互相学习，了解自己的不足)
我们反观我们的代码，还有什么可以改进的地方?
当然有很多，于是就有了这个乱搞优化Part2。
1.我们使用的前向星存图改成Vector的邻接表存图会更快:
```cpp
struct edge
{
int to,flow,next;
edge(int to,int flow,int next):to(to),flow(flow),next(next){}
};
std::vector<edge>a[1203];
```
```cpp
inline void addEdge(const int u,const int v,const int f)
{
a[u].push_back(edge(v,f,a[v].size()));
a[v].push_back(edge(u,0,a[u].size()-1));
}
```
2.我们的数组尽可能的用Vector代替，这样就可以使用一些优秀的自带函数。
3.我们不加上using namespace std，可以获得一定程度的加速。
4.我们使用c++中的list来实现快速的插入和删除。
5.由于我们会频繁地遍历，我们定义好迭代器(这一点只是为了写代码方便，而不是为了提高速度)。
```cpp
std::vector<edge>a[1203];
std::vector<int>list[1203],h,cnt,que,e;
typedef std::list<int> List;
std::vector<List::iterator>iter;
List dlist[1203];
typedef std::vector<edge>::iterator Iterator;
```
6.由于一次bfs设定高度+重贴标签效率较低，我们进行**全局重贴标签**，即一次完成所有点的重贴标签操作。
全局重贴标签的原理与一般的重贴标签类似。
```cpp
inline void relabel(int n,int t)
{
h.assign(n,n);h[t]=0;
cnt.assign(n,0);
que.clear();
que.resize(n+1);
int qh=0,qt=0;
for(que[qt++]=t;qh<qt;)
{
int u=que[qh++],het=h[u]+1;
for(Iterator p=a[u].begin();p!=a[u].end();++p)
{
if(h[p->to]==n&&a[p->to][p->next].flow>0)
{
cnt[h[p->to]=het]++;
que[qt++]=p->to;
}
}
}
for(register int i=0;i<=n;++i){list[i].clear();dlist[i].clear();}
for(register int u=0;u<n;++u)
{
if(h[u]<n)
{
iter[u]=dlist[h[u]].insert(dlist[h[u]].begin(),u);
if(e[u]>0)list[h[u]].push_back(u);
}
}
hst=(nowh=h[que[qt-1]]);
}
```
7.赋值操作大量的使用了assign函数。
8.优先队列使用了vector代替，而且用一个数组的(1203个)vector表示不同的高度。
9.push操作做了大量的更改，新的push过程有两个内容:
基于边的push(int u,edge &ed)作为push的一个子过程被调用，侧重于当前边的修改:
```cpp
inline void push(int u,edge &ed)
{
int v=ed.to;
int df=std::min(e[u],ed.flow);ed.flow-=df;
a[v][ed.next].flow+=df;
e[u]-=df;e[v]+=df;
if(0<e[v]&&e[v]<=df)list[h[v]].push_back(v);
}
```
而hlpp主过程用会调用的push(int n,int u)则侧重于同高度的点的优化。
```cpp
inline void push(int n,int u)
{
int nh=n;
for(Iterator p=a[u].begin();p!=a[u].end();++p)
{
if(p->flow>0)
{
if(h[u]==h[p->to]+1){push(u,*p);if(e[u]==0)return;}
else nh=std::min(nh,h[p->to]+1);
}
}
int het=h[u];
if(cnt[het]==1)
{
for(register int i=het;i<=hst;++i)
{
for(List::iterator it=dlist[i].begin();it!=dlist[i].end();++it){cnt[h[*it]]--;h[*it]=n;}
dlist[i].clear();
}
hst=het-1;
}
else
{
cnt[het]--;
iter[u]=dlist[het].erase(iter[u]);
h[u]=nh;
if(nh==n)return;
cnt[nh]++;
iter[u]=dlist[nh].insert(dlist[nh].begin(),u);
hst=std::max(hst,nowh=nh);
list[nh].push_back(u);
}
}
```
10.快读是一个好东西，要记得加上:
```cpp
inline int read()
{
int f=0,fu=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')fu=-1;c=getchar();}
while(c>='0'&&c<='9'){f=(f<<3)+(f<<1)+c-48;c=getchar();}
return f*fu;
}
```
剩余就没什么值得注意的，也很好理解。
不过还是把HLPP主过程单独拎出来给你们看看:
```cpp
inline int hlpp(int n,int s,int t)
{
if(s==t)return 0;
nowh=0;hst=0;
h.assign(n,0);h[s]=n;
iter.resize(n);
for(register int i=0;i<n;++i)if(i!=s)iter[i]=dlist[h[i]].insert(dlist[h[i]].begin(),i);
cnt.assign(n,0);cnt[0]=n-1;
e.assign(n,0);e[s]=INF;e[t]=-INF;
for(register int i=0;i<(int)a[s].size();++i)push(s,a[s][i]);
relabel(n,t);
for(int u;nowh>=0;)
{
if(list[nowh].empty()){nowh--;continue;}
u=list[nowh].back();
list[nowh].pop_back();
push(n,u);
}
return e[t]+INF;
}
```
值得注意的是最后一句的```e[t]+INF```。
这一句与relabel操作中的```e[t]=-INF```相对应，是为了防止**超额流**真的"超额"(溢出)了。
HLPP(改进写法)完整代码:
```cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cassert>
#include<cwchar>
#include<cwctype>
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
const int INF(INT_MAX);
struct edge
{
int to,flow,next;
edge(int to,int flow,int next):to(to),flow(flow),next(next){}
};
std::vector<edge>a[1203];
std::vector<int>list[1203],h,cnt,que,e;
typedef std::list<int> List;
std::vector<List::iterator>iter;
List dlist[1203];
typedef std::vector<edge>::iterator Iterator;
int hst,nowh;
inline void addEdge(const int u,const int v,const int f)
{
a[u].push_back(edge(v,f,a[v].size()));
a[v].push_back(edge(u,0,a[u].size()-1));
}
inline void relabel(int n,int t)
{
h.assign(n,n);h[t]=0;
cnt.assign(n,0);
que.clear();
que.resize(n+1);
int qh=0,qt=0;
for(que[qt++]=t;qh<qt;)
{
int u=que[qh++],het=h[u]+1;
for(Iterator p=a[u].begin();p!=a[u].end();++p)
{
if(h[p->to]==n&&a[p->to][p->next].flow>0)
{
cnt[h[p->to]=het]++;
que[qt++]=p->to;
}
}
}
for(register int i=0;i<=n;++i){list[i].clear();dlist[i].clear();}
for(register int u=0;u<n;++u)
{
if(h[u]<n)
{
iter[u]=dlist[h[u]].insert(dlist[h[u]].begin(),u);
if(e[u]>0)list[h[u]].push_back(u);
}
}
hst=(nowh=h[que[qt-1]]);
}
inline void push(int u,edge &ed)
{
int v=ed.to;
int df=std::min(e[u],ed.flow);ed.flow-=df;
a[v][ed.next].flow+=df;
e[u]-=df;e[v]+=df;
if(0<e[v]&&e[v]<=df)list[h[v]].push_back(v);
}
inline void push(int n,int u)
{
int nh=n;
for(Iterator p=a[u].begin();p!=a[u].end();++p)
{
if(p->flow>0)
{
if(h[u]==h[p->to]+1){push(u,*p);if(e[u]==0)return;}
else nh=std::min(nh,h[p->to]+1);
}
}
int het=h[u];
if(cnt[het]==1)
{
for(register int i=het;i<=hst;++i)
{
for(List::iterator it=dlist[i].begin();it!=dlist[i].end();++it){cnt[h[*it]]--;h[*it]=n;}
dlist[i].clear();
}
hst=het-1;
}
else
{
cnt[het]--;
iter[u]=dlist[het].erase(iter[u]);
h[u]=nh;
if(nh==n)return;
cnt[nh]++;
iter[u]=dlist[nh].insert(dlist[nh].begin(),u);
hst=std::max(hst,nowh=nh);
list[nh].push_back(u);
}
}
inline int hlpp(int n,int s,int t)
{
if(s==t)return 0;
nowh=0;hst=0;
h.assign(n,0);h[s]=n;
iter.resize(n);
for(register int i=0;i<n;++i)if(i!=s)iter[i]=dlist[h[i]].insert(dlist[h[i]].begin(),i);
cnt.assign(n,0);cnt[0]=n-1;
e.assign(n,0);e[s]=INF;e[t]=-INF;
for(register int i=0;i<(int)a[s].size();++i)push(s,a[s][i]);
relabel(n,t);
for(int u;nowh>=0;)
{
if(list[nowh].empty()){nowh--;continue;}
u=list[nowh].back();
list[nowh].pop_back();
push(n,u);
}
return e[t]+INF;
}
inline int read()
{
int f=0,fu=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')fu=-1;c=getchar();}
while(c>='0'&&c<='9'){f=(f<<3)+(f<<1)+c-48;c=getchar();}
return f*fu;
}
int n,m,s,t,u,v,f;
signed main()
{
n=read(),m=read(),s=read(),t=read();
for(register int i=m;i>0;--i){u=read(),v=read(),f=read();addEdge(u,v,f);}
printf("%d",hlpp(n+1,s,t));
return 0;
}
```