题解 P4722 【【模板】最大流 加强版 / 预流推进】
------------前言------------
这一题来发一个题解，来介绍两个重点:较慢的HLPP的写法(也是经典写法，实现起来简单)，以及那些最优解们对原做法的优化。
------------Part1.HLPP经典写法:------------
我参照第一篇题解的方法写出来的代码勉强能趁着luogu一个评测机波动卡过去，在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的节点不在网络中)，并将终点入队:
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;
}bfs过程完整代码:
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操作。
由于不是求一条路径，仅仅是取一个点和比它低的邻点，我们只需要遍历当前点的邻点:
il void push(int u)
{
re int i;
for(i=head[u];i!=-1;i=a[i].next)
{
int v=a[i].to;在这之后，我们找到每一个在网络内的比它低的节点,并将它的超额流传递给下一位。
pq是一个以节点高度为关键字的优先队列:
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号节点的超额流。
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过程完整代码:
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操作代码:
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]记录每一个高度有多少的点。
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开小的问题)，我们将源点发出的边单独拿出来进行推流。
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.我们将当前最高的点从优先队列中取出，并判断是否有超额流:
while(!pq.empty())
{
int t=pq.top();pq.pop();
vis[t]=0;push(t);
if(e[t])
{3.这里的gap优化就要起作用了，若最高点所处的层数只有它一个，我们就将其高度改为n+1层:
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.接下来就将它的标签重贴，并进行推流:
relabel(t);gap[h[t]]++;
pq.push(t);vis[t]=1;
}
}5.最后返回汇点的超额流,算法结束:
return e[ed];
}HLPP主过程完整代码:
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(经典写法)完整代码:
#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的邻接表存图会更快:
struct edge
{
int to,flow,next;
edge(int to,int flow,int next):to(to),flow(flow),next(next){}
};
std::vector<edge>a[1203];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.由于我们会频繁地遍历，我们定义好迭代器(这一点只是为了写代码方便，而不是为了提高速度)。
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设定高度+重贴标签效率较低，我们进行全局重贴标签，即一次完成所有点的重贴标签操作。
全局重贴标签的原理与一般的重贴标签类似。
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的一个子过程被调用，侧重于当前边的修改:
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)则侧重于同高度的点的优化。
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.快读是一个好东西，要记得加上:
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主过程单独拎出来给你们看看:
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(改进写法)完整代码:
#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;
}