P4722 【模板】最大流

P4722 【模板】最大流 加强版 / 预流推进

---

今日心血来潮，打算学习hlpp

然后学了一阵子。发现反向边建错了。容量并不是0.qwq

然后就荒废了一晚上。

算法流程的话。有时间补上

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using std::min;
using std::queue;
using std::vector;
using std::priority_queue;
const int N=3e4,M=3e5;
const int inf=0x3f3f3f3f;
int head[N],nxt[M<<1],flow[M<<1],p[M<<1],tail=-1;
int H[N],gap[M<<1],e[N];
bool inq[N];
int n,m,s,t;
void add(int a,int b,int c)
{p[++tail]=b;flow[tail]=c;nxt[tail]=head[a];head[a]=tail;
}
struct compare
{bool operator()(int A,int B)const{ return H[A]<H[B]; }
};
priority_queue<int,vector<int>,compare> q;
bool bfs()
{queue<int>Q;memset(H,0x3f,sizeof(H));H[t]=0;Q.push(t);while(!Q.empty()){int pas=Q.front();Q.pop();for(int i=head[pas];i!=-1;i=nxt[i])if(flow[i^1]&&H[p[i]]>H[pas]+1){H[p[i]]=H[pas]+1;Q.push(p[i]);}}return H[s]!=inf;
}
void push_flow(int now)
{for(int i=head[now];i!=-1;i=nxt[i])if(flow[i]&&H[p[i]]+1==H[now]){int F=min(e[now],flow[i]);flow[i]-=F;flow[i^1]+=F;e[now]-=F;e[p[i]]+=F;if(p[i]!=s&&p[i]!=t&&!inq[p[i]]){q.push(p[i]);inq[p[i]]=true;}if(!e[now]) break;}return ;
}
void reset(int now)
{H[now]=inf;for(int i=head[now];i!=-1;i=nxt[i])if(flow[i]&&H[p[i]]+1<H[now])H[now]=H[p[i]]+1;return ;
}
int hlpp()
{if(!bfs())  return 0;H[s]=n;memset(gap,0,sizeof(gap));for(int i=1;i<=n;i++)if(H[i]<inf)gap[H[i]]++;for(int i=head[s];i!=-1;i=nxt[i])if(flow[i]){int pas=flow[i];flow[i]-=pas;flow[i^1]+=pas;e[s]-=pas;e[p[i]]+=pas;if(p[i]!=s&&p[i]!=t&&!inq[p[i]])q.push(p[i]),inq[p[i]]=true;}while(!q.empty()){int pas=q.top();inq[pas]=false;q.pop();push_flow(pas);if(e[pas]){gap[H[pas]]--;if(!gap[H[pas]])for(int i=1;i<=n;i++)if(i!=s&&i!=t&&H[i]>=H[pas]&&H[i]<n+1)H[i]=n+1;reset(pas);gap[H[pas]]++;q.push(pas);inq[pas]=true;}}return e[t];
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);int a,b,c;for(int i=1;i<=n;i++)   head[i]=-1;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,0);}printf("%d",hlpp());
}