【模板】网络最大流 Dinic

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7ffffff
const int M = 1000005;
struct E{
	int nxt,v,w;
};
E edge[M];
int dpth[M],head[M],cnt;
int n,m,s,t;
void add(int u,int v,int w){
	cnt++;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
//初始化从0开始存边 i^1是i的反向边
void init(){
	cnt=-1;
	memset(head,-1,sizeof(head));
}
//初始化分层图
bool bfs(){
	memset(dpth,0,sizeof(dpth));
	queue<int> q;	q.push(s); dpth[s] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int v,i=head[u];i!=-1;i=edge[i].nxt){
			{
				v = edge[i].v;  
				if(edge[i].w>0&&dpth[v]==0){
					dpth[v] = dpth[u]+1;
					q.push(v);
				}
			}
		}
	}
	if(dpth[t]!=0)
	return true;
	else return false;
}
int dfs(int u,int dist){
	if(u==t)
	 return dist; 
	for(int v,i=head[u];i!=-1;i=edge[i].nxt){
		v = edge[i].v;
		if((dpth[v]==dpth[u]+1)&&edge[i].w!=0)
		{
			int di = dfs(v,min(dist,edge[i].w));
			if(di>0){
				edge[i].w-=di;
				edge[i^1].w+=di;
				return di; 
			}
		}
	}
	return 0;
}
int dinic(){
	int ans=0;
	while(bfs())
		while(int di = dfs(s,INF))
			ans+=di;
	return ans;
}
int main(){
	cin>>n>>m>>s>>t;
	init();
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,0); 
	} 
	cout<<dinic();
	return 0;
}