在网络流中我们要学会呼吸。。。
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 1.2e3+10;
constexpr int maxm = 2.4e5+10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;int n,m,s,t;struct node
{int to,w,rev;// rev反向边编号node()=default;node(int a,int b,int c):to(a),w(b),rev(c){}
};vector<node> gra[maxn];
int gap[maxn],h[maxn],exf[maxn];
stack<int> b[maxn];
int h_max;void add(int u,int v,int c)
{gra[u].emplace_back(v,c,gra[v].size());gra[v].emplace_back(u,0,gra[u].size()-1);
}bool push(int u)
{bool init=(u==s);for(auto &i : gra[u]){int &v=i.to;int &w=i.w;int &rev=i.rev;// 没有剩余容量，高度差不为1，达不到t（init用）if(!w || (!init && h[u]!=h[v]+1) || h[v]==INF) continue;int k=init ? w : min(w,exf[u]);if(v!=s && v!=t && !exf[v])// 不是是s，t，可能有能力继续推{// 如果还有超额流，那一定不能往下推b[h[v]].emplace(v);// 对应高度的桶h_max=max(h_max,h[v]);// 记录最高高度}exf[u]-=k;// 调整超额流exf[v]+=k;w-=k;gra[v][rev].w+=k;if(!exf[u]) return 0;// 不溢出，不用relabel}return 1;
}bool bfs()
{memset(h,63,sizeof(int)*(n+3));queue<int> q;q.emplace(t);// 从t（h=0）开始h[t]=0;while(!q.empty()){int u=q.front(); q.pop();for(auto &i : gra[u]){int &v=i.to;int &rev=i.rev;if(gra[v][rev].w && h[v]>h[u]+1)// t->s的反向边（s->t）有余量{h[v]=h[u]+1;q.emplace(v);}}}return h[s]!=INF;// 判断能否到s
}int get_h_max()
{while(~h_max && b[h_max].empty()) --h_max;return ~h_max ? b[h_max].top() : 0;
}void relabel(int u)
{h[u]=INF;for(auto &i : gra[u]){if(i.w) h[u]=min(h[u],h[i.to]);// u高度升为最小邻居+1}++h[u];if(h[u]<n){// 维护一下高度相关的优化b[h[u]].emplace(u);h_max=max(h_max,h[u]);++gap[h[u]];}
}int hlpp()
{if(!bfs()) return 0;memset(gap,0,sizeof(int)*(n+10));//需要一点冗余因为会有部分设为n+1回流时h变高for(int i=1;i<=n;++i){if(h[i]!=INF) ++gap[h[i]];// 初始化gap}h[s]=n;push(s);// 初始化int u;while((u=get_h_max()))// 取出有超额流的h最高的点{b[h_max].pop();if(push(u)){// 仍然溢出，高度一定改变if(!--gap[h[u]])// 如果断层，所有在区间内的点都不可能到t{for(int i=1;i<=n;++i){if(i!=s && h[i]>h[u] && h[i]<n+1){h[i]=INF;}}}relabel(u);}}return exf[t];
}signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endifscanf("%lld%lld%lld%lld",&n,&m,&s,&t);for(int i=1,u,v,c; i<=m;++i){scanf("%lld%lld%lld",&u,&v,&c);add(u,v,c);}int ans=hlpp();printf("%lld\n",ans);return 0;
}