常用优化：
- 分层时遇到汇点直接返回（一方面可以减少分层时的运算量，另一方面可以加速Dinic的运行）
- Dinic时无余量直接返回（如果不返回会造成大量的冗余运算）
- 不分层的Dinic是没有灵魂的
易错点：
- 不在汇点返回的Dinic如同被堵住的下水道.
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
int n;
struct Edge{
int from,to,w,nxt;
}e[MAXM];
int head[MAXN];
int edgeCnt=1;//反向边，所以边计数从1开始
void addEdge(int u,int v,int w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
int s,t;
int d[MAXN];//层数
bool bfs(){
queue<int> q;
for(int i=1;i<=n;i++){
d[i]=0;
}
q.push(s);d[s]=1;
while(!q.empty()){
int nowNode=q.front();q.pop();
for(int i=head[nowNode];i;i=e[i].nxt){
int v=e[i].to;
if(!d[v]&&e[i].w>0){
q.push(v);
d[v]=d[nowNode]+1;
if(v==t)return true;
}
}
}
return d[t]!=0;
}
int Dinic(int x,int flow){
if(x==t)return flow;
int rest=flow;
for(int i=head[x];i&&rest;i=e[i].nxt){
int v=e[i].to;
if(d[v]==d[x]+1&&e[i].w!=0){
int k=Dinic(v,min(rest,e[i].w));
if(!k)d[v]=0;
e[i].w-=k,e[i^1].w+=k;
rest-=k;
}
}
return flow-rest;
}
int INF=1<<30;
int main(){
int m;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,0);
}
int nowFlow,ans=0;
while(bfs()){
ans+=Dinic(s,INF);
}
cout<<ans<<endl;
return 0;
}