吐槽
这个算法。。
怎么说........
学来也就是装装13吧。。。。
长得比EK丑
跑的比EK慢
写着比EK难
思想
大家先来猜一下这个算法的思想吧:joy:
看看人家的名字——最高标号预留推进
多么高端大气上档次2333333咳咳
从它的名字中我们可以看出，它的核心思想是—推进，而不是找增广路
那么它是怎么实现推进的呢？
很简单，我们从源点开始，不停的向其他的点加流量，对于每个点都如此操作。那么推到最后，我们就可以得到到达汇点的最大流量
不过可能会出现一种情况，就是$A$送流量给$B$，$B$觉得不好意思不想要，于是又推给$A$，$A$非常热情便又推给$B$……直到推到TLE为止。。那怎么解决这种情况呢？
我们对每个点，引入一个高度$H$，并且规定，一个点$u$可以向另一个点$v$送流量，当且仅当$H[u]=H[s]+1$
这样我们就可以保证不会有上面情况发生了
另外还有一种情况，就是这个点依然有流量，但是迫于高度的限制流不出去，那怎么办呢？
很简单，我们增加这个点的高度，这样这个点的流量就能流出去了。
优化
预留推进也就是这些内容了
但是它的名字里的最高标号是啥意思呢？
这个要感谢咱们的熟人tarjan，他和他的小伙伴发现，如果每次选的点是高度最高的点，时间复杂度会更优。
可以优化至$O(n^2\sqrt{m})$
另外还有一个比较显然的优化，如果一个高度$i$是不存在的，即图中没有高度为$i$的点，那么从比$i$高的点一定不会走到汇点$T$，因为根据我们的限制条件，必须要经过高度为$i$的点，于是这些点就没有用了
代码
不是我说，这个算法真的是死慢死慢的，，，，
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN=*1e3+;
const int INF=1e8+;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=nc();}
while(c>=''&&c<=''){x=x*+c-'';c=nc();}
return x*f;
}
int N,M,S,T;
int H[MAXN];//每个节点的高度
int F[MAXN];//每个节点可以流出的流量
int gap[MAXN];//每个高度的数量
struct node
{
int u,v,flow,nxt;
}edge[MAXN];
int head[MAXN];
int num=;//注意这里num必须从0开始
inline void add_edge(int x,int y,int z)
{
edge[num].u=x;
edge[num].v=y;
edge[num].flow=z;
edge[num].nxt=head[x];
head[x]=num++;
}
inline void AddEdge(int x,int y,int z)
{
add_edge(x,y,z);
add_edge(y,x,);//注意这里别忘了加反向边
}
struct comp
{
int pos,h;
comp(int pos=,int h=):pos(pos),h(h) {}
inline bool operator < (const comp &a) const {return h<a.h;}
};
priority_queue<comp>q;
bool Work(int u,int v,int id)
{
int val=min(F[u],edge[id].flow);
edge[id].flow-=val;edge[id^].flow+=val;
F[u]-=val;F[v]+=val;
return val;
}
inline int HLPP()
{
H[S]=N;F[S]=INF;q.push(comp(S,H[S]));
while(q.size()!=)
{
int p=q.top().pos;q.pop();
if(!F[p]) continue;
for(int i=head[p];i!=-;i=edge[i].nxt)
if( (p==S||H[edge[i].v]+==H[p]) && Work(p,edge[i].v,i) && edge[i].v!=S && edge[i].v!=T)
q.push( comp(edge[i].v,H[edge[i].v]) );
if(p!=S && p!=T && F[p])
{
if( (--gap[ H[p] ])== )//该高度不存在
{
for(int i=;i<=N;i++)
if( H[p]<H[i]&&H[i]<=N && p!=S && p!=T )
H[i]=N+;//设置为不可访问
}
++gap[ ++H[p] ];//高度+1
q.push( comp(p,H[p]) );
}
}
return F[T];
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
memset(head,-,sizeof(head));
N=read(),M=read(),S=read(),T=read();
for(int i=;i<=M;i++)
{
int x=read(),y=read(),z=read();
AddEdge(x,y,z);
}
printf("%d", HLPP() );
return ;
}