今日心血来潮，打算学习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());
}