网络流-最大流

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int n,m,s,t,idx=1,head[N],cur[N],dis[N];//idx初始为1，从2.3开始配对 
struct node{
	int u,v,w,nxt;
}g[N];
void add(int u,int v,int w){
	g[++idx]={u,v,w,head[u]};head[u]=idx;
	g[++idx]={v,u,0,head[v]};head[v]=idx;//反向建边 
}
bool bfs(){//寻找增广路 
	memset(dis,0,sizeof(dis));
	queue<int>q;q.push(s);dis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop(); 
		for(int i=head[u];i;i=g[i].nxt){
			int v=g[i].v;
			if(dis[v]==0&&g[i].w){
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==t) return 1;
			}
		}
	} 
	return 0;
}
int dfs(int u,int mf){//多路增广 
	if(u==t) return mf;
	int sum=0;
	for(int &i=cur[u];i;i=g[i].nxt){//当前弧优化 
		int v=g[i].v;
		if(dis[v]==dis[u]+1&&g[i].w){
			int f=dfs(v,min(mf,g[i].w));
			g[i].w-=f;
			g[i^1].w+=f;
			sum+=f;//累加流出流量 
			mf-=f;//减少流量剩余 
			if(mf==0) break;//如果没流量了就停止 
		}
	}
	if(sum==0) dis[u]=0;//残枝优化，删点 
	return sum;
}
int dinic(){//将可行流累加 
	int ans=0;
	while(bfs()){
		memcpy(cur,head,sizeof(head));
		ans+=dfs(s,1e9);//初始可行流流量为无穷大 
	}
	return ans;
}
signed main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		add(u,v,w);
	}
	cout<<dinic();
    return 0;
}