MnZn 求助:玄学RE
查看原帖
MnZn 求助:玄学RE
372299
超级玛丽王子楼主2021/2/27 21:34

RT,之前忘了开 ll 还得了 64 分,开完就全 RE 了……

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9,N=250;
int n,m,s,t,g[N][N],pre[N];
int bfs()  {
	int flow[N];
	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<=m;++i)
			if(i^s&&g[u][i]&&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];
}
int mflow() {
	int Mflow=0;
	while(true) {
		int f=bfs();
		if(f==-1) break;
		int cur=t;
		while(cur^s) {
			int fa=pre[cur];
			g[fa][cur]-=f;
			g[cur][fa]+=f;
			cur=fa;
		}
		Mflow+=f;
	}
	return Mflow;
}
signed main(void) {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<m;++i) {
		int u,v,w;
		scanf("%d%d%lld",&u,&v,&w);
		g[u][v]+=w;
	}
	printf("%lld\n",mflow());
	return 0;
}

2021/2/27 21:34
加载中...