连网络流都不会了/kk
查看原帖
连网络流都不会了/kk
223392
Belarus楼主2020/6/19 10:13

如题,好久没复习了,凭印象打出来 30 分,和之前的比对了一下好像没有太大的问题,也不知道哪里错了?

#include<bits/stdc++.h>
using namespace std;
const int size=500010;
int n,m,s,t,maxflow=0;
int ver[size],head[size],edge[size],nxt[size],tot=1;
int d[size];
inline void add(int x,int y,int z){
	ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
	ver[++tot]=z;edge[tot]=0;nxt[tot]=head[y];head[y]=tot;
}
inline bool bfs(){
	memset(d,0,sizeof(d));
	queue<int> q;
	while(!q.empty()) q.pop();
	d[s]=1;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i],z=edge[i];
			if(z&&(!d[y])){
				d[y]=d[x]+1;
				q.push(y);
				if(y==t) return 1;
			}
		}
	}
	return 0;
}
int dinic(int x,int flow){
	if(x==t) return flow;
	int used=0,f;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i],z=edge[i];
		if(z&&d[y]==d[x]+1&&used<flow){
			used+=dinic(y,min(flow-used,z));
			edge[i]-=used;
			edge[i^1]+=used;
		}
	}
	if(!used) d[x]=0;
	return used;
}
int main(){
	//freopen("P3376_4.in.txt","r",stdin);
	ios::sync_with_stdio(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	int tmp;
	while(bfs()) 
	 while(tmp=dinic(s,0x3f3f3f3f)) 
	  maxflow+=tmp;
	cout<<maxflow;
	return 0;
}
2020/6/19 10:13
加载中...