Decribe:
给定 \(n\) 个点 \(m\) 条边，每条边有一个流量 \(f\)。给定起点 \(s\) 和终点 \(t\)，求最大流。（\(n \le 1200 , m \le 120000\)）
Solution:
当 \(n,m\) 来到这样一个上界，Dinic 稍稍被卡就过不去了，与其研究奇奇怪怪的 Dinic 优化，真不如学一个 HLPP，它又不难。（又不会吃掉你）
学过 ISAP 会更好学 HLPP，它们之间有许多的共性。
我们先回忆一下 Dinic 的运行过程：先找到一条或几条增广路，推送流量，再重新找增广路，推送流量，直至找不到增广路为止。这样的算法因为 spfa 的原因，可以卡到 \(O(n^2m)\)，（如果没有当前弧优化的话，那将是 \(O(nm^2)\)）这是难以接受的。每次寻找增广路时，都有大量的时间浪费在无用的路径。因此就有了 ISAP，它就在推送流量的 dfs 中，尝试更新增广路，因此往往也更快。（但时间复杂度实际是相同的）
推流方案
但这还不够快。于是 HLPP 出现了，时间复杂度上界仅有 \(O(n^2\sqrt m)\)。（没用当前弧优化的话，当然是 \(O(nm\sqrt m)\)）让我们回归最初的想法。一开始接触到最大流时，应该有很多人的想法是让流量同时从起点全部流出，看能到达多少。HLPP 基本遵循了这个想法。首先先从起点无视流量守恒，全部推流出去，每个被推流的点获得一个余流。再遍历每个有余流的点，将余流推流。但是流向何处呢？若不加以限制，势必会出现两个点和一条边打乒乓球，你流过来，我流过去，获得一个完美的 TLE。
确定流向
想想增广路是怎么确定路线的？通过每一次的 spfa，对每个点标记分层图高度，规定流量只能从上往下流。而 ISAP 中增广一次后，让每个推流过的点向上爬，尝试找到新的增广路。于是我们也可以给定每个点一个高度，规定流量只能从上往下一层一层的流，就像水往低处流一样。如果已经没有合适的路径了，就尝试遍历每条仍有流量的边对应的点，更新为 \(\text{最低点}+1\)，这样可以保证有新的一条路可以推流，也不会漏掉某些还未推流的边。相比于 ISAP 的一层层爬，效率可谓是天差地别。
减少推流次数
为减少推流次数，显然从高到低的顺序推流可以最大程度减少推流的次数，因此可以用一个以高度为排序键值的大根堆优先队列存点，每次取队头推流。
一些小细节
最终的网络还是要遵循流量守恒的。也就是说，多余的流量最终会回到起点。所以起点的高度要定为 \(n\)，这样既不会一开始就流回来，也不会增加太多的推流次数。
起点和终点是不能入队的。起点有无限余流，终点没有余流。
To be better
但这样只是最基础的 HLPP，非常容易达到上界，甚至在随机图的效率远不如 Dinic。我们需要加亿一点点的优化，以食用更好的 HLPP。
gap 优化
既然类比于 ISAP 的爬层，那为什么不能把 ISAP 的 gap 优化拿来用？若某一高度已经没有点了，即断层，那显然高度更高的点已经无法推流向终点了。若是只需要终点的信息，则可以无视更高的点了。若需要整个图的信息，那就得让更高的点流回起点返还，直接全部设为 \(n+1\) 即可。
如果使用 gap 优化（应该没有人不用吧ˋ( ° ▽、° ) ），还有个小细节需要注意：在入队时可能会有高度为 \(inf\) 的点，会导致 RE，应在入队时排除。
vector 是个好东西
一般要卡掉 Dinic 而用 HLPP 时，网络往往很稠密，不连续访存的邻接表会有很大的常数。这时可以改用 vector 存图，连续的访存拥有极小的常数。
邻接表：4.73s
vector：1.08s
好用极了！d=====(￣▽￣*)b
bfs 初始化
在一开始设置高度的时候，要从 \(0\) 慢慢往上爬，显然浪费了太多的时间。所以可以先从终点 bfs 一遍设置高度，从第一次推流就可以找到路，少了许多进队出队重编号的时间。
叠完 buff 之后，现在的 HLPP 即使在随机图上也不逊色于 Dinic 和 ISAP 了，可供诸君任意使用。
Code:
以下代码加了所有以上优化。
bool _Start;// by Lofty
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
#ifdef DEBUG
#define gc() (getchar())
#else
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef DEBUG
void pc(const char &c)
{O
putchar(c);
}
#else
char pbuf[1<<20],*pp=pbuf;
void pc(const char &c)
{
if(pp-pbuf==1<<20)
fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
*pp++=c;
}
struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
#endif
TP void read(T &x)
{
x=0;static int f;f=0;static char ch;ch=gc();
for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch^48);
f&&(x=-x);
}
TP void write(T x)
{
if(x<0)
pc('-'),x=-x;
static T sta[35],top;top=0;
do
sta[++top]=x%10,x/=10;
while(x);
while(top)
pc(sta[top--]^48);
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void writeln(const T x){write(x);pc('\n');}
TP void writesp(const T x){write(x);pc(' ');}
TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
TP void debugsp(const T x){fprintf(stderr,"%d ",x);}
TP void debug(const T x){fprintf(stderr,"%d\n",x);}
TP_ void debug(const T x,const T_...y){debugsp(x);debug(y...);}
TP inline T max(const T &a,const T &b){return a>b?a:b;}
TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));}
TP inline T min(const T &a,const T &b){return a<b?a:b;}
TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
TP inline T abs(const T &a){return a>0?a:-a;}
#undef TP
#undef TP_
}
using namespace IO;
using std::cerr;
using PII=std::pair<int,int>;
using LL=long long;
constexpr int N=5e3+10,M=3e5+10,inf=0x3f3f3f3f;
int n,m,st,ed;
LL w[N];
int h[N],gap[N<<1],cur[N];
struct edge
{
int y;LL f;int other;
};
std::vector<edge>a[N];
inline void ins(int x,int y,LL f)
{
a[x].push_back({y,f,(int)a[y].size()});
a[y].push_back({x,0,(int)a[x].size()-1});
}
struct cmp
{
inline bool operator()(const int &x,const int &y)const
{
return h[x]<h[y];//队内高度不会改变，必须先出队再改，优先队列只在插入和出队时排序
}
};
bool bfs()//给所有点一个初始的高度，选择最短路的原因是推流的点最少
{
static std::queue<int>q;
memset(h,0x3f,sizeof(h));
h[ed]=1;
q.push(ed);
while(q.size())
{
int x=q.front();q.pop();
for(auto k:a[x])
{
int y=k.y;
if(a[y][k.other].f&&h[y]>h[x]+1)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[st]!=h[0];
}
bool inq[N];
std::priority_queue<int,std::vector<int>,cmp>q;//按高度排序的大根堆
inline void push(int x)//对 x 点的余流推流出去
{
for(int &i=cur[x];i<(int)a[x].size();i++)//当前弧优化，若保留了当前弧，说明目前余流不足，还可以需要再推流
{
edge &k=a[x][i];
int y=k.y;
if(k.f&&h[y]==h[x]-1)//可以流且是一条合法的推流路径
{
LL f=min(w[x],k.f);
w[x]-=f;w[y]+=f;
k.f-=f;
a[y][k.other].f+=f;
if(y!=st&&y!=ed&&!inq[y])//加入队列。注意起点和终点不能入队，因为起点有无限余流，终点只接收，没有余流
q.push(y),inq[y]=1;
if(!w[x])//没有余流可推了，自然要提前结束
return ;
}
}
cur[x]=0;//如果还有余流，就再重新遍历，对应下面改变高度，流向新的路径
}
inline void relabel(int x)//重新给一个高度
{
h[x]=inf;
for(auto k:a[x])
if(k.f&&h[k.y]+1<h[x])//往尽量低处流，因为最低点是终点
h[x]=h[k.y]+1;
}
LL HLPP()
{
if(!bfs())//提前给定高度，加速推流，否则需要再推流时给定，增加遍历数量
return 0;
for(int i=1;i<=n;i++)
if(h[i]<inf)
++gap[h[i]];//gap 优化，若一个高度已经全部流完，更高的是找不到低处流的
//并且 gap 需要开到 2n-1，最极端的情况可能会全部流回起点
h[st]=n;//若其他点流完找不到低处，就要流回起点方向，为防可能流向其他方向，应定为 n，这样其他点在初始情况下是不可能高于起点的
for(auto &k:a[st])//在起点做一次无限流量的推流
{
int y=k.y;
if(k.f&&h[y]<inf)
{
LL f=k.f;
w[st]-=f;w[y]+=f;
k.f-=f;
a[y][k.other].f+=f;
if(y!=st&&y!=ed&&!inq[y])//加入队列。注意起点和终点不能入队，因为起点有无限余流，终点只接收，没有余流
q.push(y),inq[y]=1;
}
}
while(q.size())
{
int x=q.top();q.pop();inq[x]=0;
push(x);
if(w[x])
{
if(--gap[h[x]]<=0)//没有该高度了
for(int i=1;i<=n;i++)
if(i!=st&&i!=ed&&h[i]>h[x]&&h[i]<n+1)//那么比它更高的就没有低处流了，流回起点
h[i]=n+1;
relabel(x);++gap[h[x]];
q.push(x);inq[x]=1;
}
}
return w[ed];
}
bool _End;
int main()
{
// fprintf(stderr,"%.2 MBlf\n",(&_End-&_Start)/1048576.0);
read(n,m,st,ed);
for(int i=1,x,y,f;i<=m;i++)
{
read(x,y,f);
ins(x,y,f);
}
writeln(HLPP());
return 0;
}