想问最大流算法的一些问题
查看原帖
想问最大流算法的一些问题
119638
xia0ji233楼主2022/2/28 14:42

如题,本蒟蒻最近在学网络流算法,所以虽然这题有更优的解法我还是比较希望能练习一下网络流算法的。这个算法是根据自己看的一些理论概念自己写的,但是貌似出了问题,个人感觉已经没什么问题了。。。求求神犇们帮忙指正一下!!

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
struct eee{
	int next;
	int to;
	int w;
}edge[maxn<<1];
int r,n,cnt=1,root[maxn],fa[maxn],dest[maxn];
stack<int>path;
inline void add(int x,int y,int w){
	edge[++cnt]={root[x],y,w};
	root[x]=cnt;
}

void dfs(int u){
	for(int i=root[u];i;i=edge[i].next){
		int to=edge[i].to;
		if(fa[u]==to)continue;
		fa[to]=u;
		//edge[i^1].w=0;
		dfs(to);
	}
	if(!edge[root[u]].next&&u!=r){
		dest[u]=1;
	} 
}

int find_path(int now,int from,int flow){
//	printf("now=%d from=%d flow=%d\n",now,from,flow);
//	printf("%d\n",dest[now]); 
	if(dest[now])return flow;
	int qw=0;
	for(int i=root[now];i;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		
		//printf("to is %d w is %d\n",to,w);
		if(to==from)continue;
		if(w==0)continue;
		path.push(i);
		qw=find_path(to,now,min(flow,w));
		break;
	}
	return qw;
}

void maxflow(){
	int ans=0;
	while(1){

		int l=find_path(r,0,0x7fffffff);
		if(l!=0&&l!=0x7fffffff){
			ans+=l;
			while(path.size()){
				int e=path.top();
				path.pop();
				edge[e].w-=l;
				edge[e^1].w+=l; 
			}
		}
		else{
			break;
		}
	} 
	
	printf("%d\n",ans);
	
}
2022/2/28 14:42
加载中...