记录编号	605094	评测结果	WWWWEE
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	0
用户昵称	秋_Water	是否通过	未通过
代码语言	C++	运行时间	0.319 s
提交时间	2025-08-13 21:15:05	内存使用	3.61 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=1e9;
const int N=250;
int n,m;
ll g[N][N],pre[N];
ll flow[N];
ll bfs(int s,int t){
	memset(pre,-1,sizeof(pre));
	flow[s]=INF;
	pre[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==t){
			break; 
		}
		for(int i=1;i<=n;i++){
			if(i!=s&&g[u][i]>0&&pre[i]==-1){
				pre[i]=u;
				q.push(i);
				flow[i]=min(flow[u],g[u][i]);
			}
		}
	}
	if(pre[t]==-1) return -1;
	return flow[t]; 
}
ll maxflow(int s,int t){
	ll flowans=0;
	while(1){
		ll newflow=bfs(s,t);
		if(newflow==-1) break;
		int cur=t;
		while(cur!=s){
			int fa=pre[cur];
			g[fa][cur]-=newflow;
			g[cur][fa]+=newflow;
			cur=fa;
		} 
		flowans+=newflow; 
	}
	return flowans;
}
int main(){
	int s,t;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w; 
		g[u][v]+=w;
	} 
	cout<<maxflow(s,t);
	

	return 0;
}