76分求调
查看原帖
76分求调
1286552
ice_shooter楼主2025/6/19 20:01
#include<bits/stdc++.h>
using namespace std;
long long g[205][205];
long long n,m,s,e;
long long vis[205];
bool bfs(){
	memset(vis,0,sizeof vis);
	queue<long long> q;
	q.push(s);
	vis[s]=-1;
	while(q.size()){
		long long u=q.front();
		if(u==e){
			return 1;
		}q.pop();
		for(long long v=1;v<=n;v++){
			if(g[u][v] && !vis[v]){
				vis[v]=u;
				q.push(v);
			}
		}
	}return 0;
}
long long NK(){
	long long sum=0;
	while(bfs()){
		long long mini=1e18;
		for(long long i=e;i!=s;i=vis[i]){
			mini=min(mini,g[vis[i]][i]);
		}for(long long i=e;i!=s;i=vis[i]){
			g[vis[i]][i]-=mini;
			g[i][vis[i]]+=mini;
		}sum+=mini;
	}return sum;
}
int main(){
	cin>>n>>m>>s>>e;
	for(long long i=1;i<=m;i++){
		long long x,y,z;
		cin>>x>>y>>z;
		g[x][y]=z;
	}cout<<NK();
	return 0;
}

WA#9 #10 #11

2025/6/19 20:01
加载中...