网络流模板求调
  • 板块灌水区
  • 楼主Zq_water
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/8 19:23
  • 上次更新2023/11/2 22:18:54
查看原帖
网络流模板求调
895435
Zq_water楼主2023/9/8 19:23

P3376,样例都过不去

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
const int maxm = 5005;
#define int long long 

int n,m,s,t,ans,cnt=-1;
int dis[maxn],vis[maxn],pre[maxn],head[maxn],f[maxn][maxn];
struct Edge{
	int to,next,w;
}edge[maxm<<1];

void add(int u,int v,int w){
	edge[++cnt]={v,head[u],w};
	head[u]=cnt;
}

bool EK(){
	memset(vis,0,sizeof vis);
	queue <int> q;q.push(s);
	vis[s]=1,dis[s]=1e15;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to,w=edge[i].w;
			if(!w||vis[v]) continue;
			dis[v]=min(dis[u],edge[i].w);
			pre[v]=i,vis[v]=1;
			if(v==t) return 1;
		}
	}
	return 0;
}

void flowup(){
	int x=t;
	while(x!=s){
		int v=pre[x];
		 edge[v].w-=dis[t];
		 edge[v^1].w+=dis[t];
		 x=edge[v^1].to;
	}
	ans+=dis[t];
}

signed main(){
	scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%lld %lld %lld",&u,&v,&w);
		if(!f[u][v]) add(u,v,w),add(v,u,0),f[u][v]=cnt;
		else edge[f[u][v]-1].w+=w;
	}
	while(EK()) flowup();
	printf("%lld",ans);
	return 0;
}
2023/9/8 19:23
加载中...