HLPP（最高标号预流推进）
传送门
HLPP
它是 Dinic 进阶的思想。
因为 Dinic 的复杂度满足不了本题了，就需要更高级的算法：HLPP 是目前网络流最大流的最先进的算法了（起码目前是的）。
思路
仍要将整个图分层，但这次抽象的分成高度的图，将汇点定义为
我们知道的是高处的水可以流向低处（常识）。那么我们将源点看成真正的“源泉”，有无穷的水。往下流（限制是每条路的最大流量），如果一个节点的流量用完了，就是说水到了之后，无路可流了，我们就将这个点的高度从新赋成最大值，这样原来能流向它的点，也由于“地势”的变化，流不过去。（简单来说，就是扔掉了这个点。）
我们不难发现一个事实：从高处流下来的水可能继续向下流。所以我们可以先将高处的水能流的全部流完，然后再流低处的水，这样流低处水的时候，“顺带”流走了高出积累下来的水。然后由于地势的提高（被提高地势的节点会越来越多，直到不能流为止。）最后会返回源点。
而汇点能流过来的量就是“最大流量”。
优化：
由于我们根据的高度进行的点的分层，所以会出现一种情况：一层（同一高度）只剩一个点了，但是这个点已经无路可流了，那么它被提高的同时意味着，比它高的所有的点都已经没用了。
代码思路
-
加边（双向边）
-
分层（节点设置高度）
-
统计同一高度节点数量（方便判断上面所说的“优化”）
-
枚举源点的流程（源点的水是无尽的所以特殊处理）
-
处理所有节点流量情况（我们可以开一个优先队列，然高度高的先处理）
-
判断“断层”情况（上面所说的“优化”）
-
输出最终流向汇点的“量”
代码
注：本篇代码本着“原汁原味”，没有别的题解的玄学优化，所以时间复杂度会差一些。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cctype>
#include<queue>
#include<vector>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=4e5+10;
struct po{
int n_t;
int v;//下一个节点
long long l;//流量
}p_p[o_o];
int h_d[o_o],x_p=1;
int n=r_r(),m=r_r(),s=r_r(),t=r_r();
void a_d(int u,int v,long long l){//建边
p_p[++x_p].v=v;
p_p[x_p].l=l;
p_p[x_p].n_t=h_d[u];
h_d[u]=x_p;
}
int h_t[o_o];//节点高度
queue<int>q_q;
long long s_v[o_o];//节点剩余的“量”
int b_b[o_o];//标记节点是否已经遍历过（防止跑环）
int g_p[o_o];//当前高度有多少节点
struct pp{
bool operator()(int a,int b)const{
return h_t[a]<h_t[b];
}
};
priority_queue<int,vector<int>,pp>p_q;
bool b_f(){//分层图
memset(h_t,0x3f,sizeof h_t);//初始化高度数组
h_t[t]=0;//从汇点开始提高度
q_q.push(t);
while(!q_q.empty()){
int k_k=q_q.front();
q_q.pop();
for(int i=h_d[k_k];i;i=p_p[i].n_t){//枚举出边
int v=p_p[i].v;
if(p_p[i^1].l&&h_t[v]>h_t[k_k]+1){//因为是往回找，所以判断反向弧
h_t[v]=h_t[k_k]+1;//更新高度，使高度尽量小
q_q.push(v);//入队
}
}
}
return h_t[s]!=h_t[0];//源点汇点是否联通
}
void x_l(int k){//节点“量”下流
for(int i=h_d[k];i;i=p_p[i].n_t){//枚举出边
int v=p_p[i].v;
if(p_p[i].l&&h_t[v]+1==h_t[k]){//边有流量并且深度是顺着下一层
int a_s=min(s_v[k],p_p[i].l);
p_p[i].l-=a_s;//更新边流量
p_p[i^1].l+=a_s;//更新反向弧流量
s_v[k]-=a_s;//更新节点剩余的“量”
s_v[v]+=a_s;//更新下一节点的“量”
if(v!=s&&v!=t&&!b_b[v]){//流向的不是源点不是汇点并且没遍历过
p_q.push(v);//入队
b_b[v]=1;//标记
}
if(!s_v[k])break;//没有流量了，退出
}
}
return ;
}
void n_h(int k_k){
h_t[k_k]=h_t[0];//将节点初始化为“不可到达”节点
for(int i=h_d[k_k];i;i=p_p[i].n_t){//枚举出边
int v=p_p[i].v;
if(p_p[i].l&&h_t[v]+1<h_t[k_k])//有可以流的边
h_t[k_k]=h_t[v]+1;//更新高度，尽可能的小
}
return ;
}
int main(){
for(int i=1;i<=m;i++){
int a=r_r(),b=r_r();
long long v=r_r();
a_d(a,b,v);//建边
a_d(b,a,0);//建反向弧
}
if(!b_f()){//源点汇点不连通直接返回
puts("0");
return 0;
}
h_t[s]=n+1;//源点提到最高的位置
memset(g_p,0,sizeof g_p);//高度节点数初始化为 0
for(int i=1;i<=n;i++)if(h_t[i]!=h_t[0])g_p[h_t[i]]++;//如果节点高度没有被扔掉，说明可以流到，当前高度节点数量增加 1
//处理源点的流动
for(int i=h_d[s];i;i=p_p[i].n_t){
int a_s=p_p[i].l;
int v=p_p[i].v;
p_p[i].l-=a_s;//更新边流量
p_p[i^1].l+=a_s;//更新反向弧流量
s_v[s]-=a_s;//更新节点剩余的“量”
s_v[v]+=a_s;//更新下一节点的“量”
if(v!=s&&v!=t&&!b_b[v]){//流向的不是源点不是汇点并且没遍历过
p_q.push(v);//入队
b_b[v]=1;//标记
}
}
//处理每个节点
while(!p_q.empty()){
int k_k=p_q.top();
p_q.pop();
b_b[k_k]=0;//删除标记
x_l(k_k);//节点下流
if(s_v[k_k]){//当前节点仍有流量
if(!--g_p[h_t[k_k]])//当前深度没有别的节点
for(int i=1;i<=n;i++)//枚举所有节点
if(i!=s&&i!=t&&h_t[i]>h_t[k_k]&&h_t[i]<n+1)//不为源点和汇点并且比当前节点高度大且没有被扔掉
h_t[i]=n+1;//将可以到达它的节点扔掉
n_h(k_k);//更新节点高度
++g_p[h_t[k_k]];//当前深度的节点增加 1
p_q.push(k_k);//入队
b_b[k_k]=1;//标记
}
}
printf("%d\n",s_v[t]);//输出最终流向汇点的“量”
return 0;
}