最大流模板dinic

复杂度o n^2m
思路：bfs出分层图，不断dfs，用当前弧优化。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
const int M=200010;
int h[N],e[M],ne[M],f[M];
int cur[N],d[N];
int q[N],idx;
int n,m,S,T;
void add(int a,int b,int c)
{
   
	e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
	ne[idx]=h[b],f[idx]=0,e[idx]=a,h[b]=idx++;
}
bool bfs()
{
   
	memset(d,-1,sizeof d);
	d[S]=0;
	int tt=0,hh=0;
	q[0]=S;
	cur[S]=h[S];
	while(hh<=tt)
	{
   
		int t=q[hh++];
		for(int i=h[t];~i;i=ne[i])
		{
   
			int j=e[i];
			if(d[j]==-1 && f[i])
			{
   
				d[j]=d[t]+1;
				cur[j]=h[j];
				if(j==T)	return true;
				q[++tt]=j;
			}
		}
	}
	return false;
}
int dfs(int u,int limit)
{
   
	if(u==T)
	return limit;
	int flow=0;
	for(int i=cur[u];~i&&flow<limit;i=ne[i])
	{
   
		int j=e[i];
		cur[u]=i;
		if(d[j]==d[u]+1 && f[i])
		{
   
			int t=dfs(j,min(f[i],limit-flow));
			if(!t)	d[j]=-1;
			flow+=t,f[i]-=t,f[i^1]+=t;
		}
	}
	return flow;
}
int dinic()
{
   
	int flow,res=0;
	while(bfs())
	while(flow=dfs(S,1000000))
	res+=flow;
	return res;
}
int main()
{
   
	memset(h,-1,sizeof h);
	cin>>n>>m>>S>>T;
	while(m--)
	{
   
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<<dinic()<<endl;
	return 0;
}