请求加强数据
查看原帖
请求加强数据
701408
lao_wang楼主2024/5/6 15:50

我的代码

bool bfs(){
	for(int i=1;i<=n;i++) now[i] = head[i] , dep[i] = 0x3f3f3f3f3f3f , vis[i] = 0 ;
	q.push(s) ;
	dep[s] = 0 ;
	while(!q.empty()){
		int u=q.front() ;
		q.pop() ;
		vis[u] = 0 ;
		for(int i=head[u];~i;i=G[i].next){
			int x=G[i].to ;
			if(dep[x]<=dep[u]+1||!G[i].w) continue ;
			dep[x] = dep[u]+1 ;
			if(!vis[x]){
				vis[x] = 1 ;
				q.push(x) ;
			}
		}
	}
	return dep[t]!=0x3f3f3f3f3f3f ;
}
int dfs(int u,int minn){
	if(u==t){ vis[u]=1 ;return minn ; }
	if(vis[u]) return 0 ;
	vis[u] = 1 ;
	int use=0 ;
	for(int i=now[u];~i;i=G[i].next){
		now[u] = i ;
		int x=G[i].to ;
		if(!G[i].w||dep[x]!=dep[u]+1) continue ;
	    int temp = dfs(x,min(minn,G[i].w)) ;
		if(!temp) continue ;
		G[i].w -= temp ;
		G[i^1].w += temp ;
		use += temp ;
		if(use==minn) break; 
	}
	return use ;
}
int dinic(){
	long long ans=0 ;
	while(bfs()){
 	    	int temp=dfs(s,2147483647) ;
	    	ans += temp ;
	}
	return ans ;
}

其中 dfs(x,min(minn,G[i].w)) 原本应该为 dfs(x,min(minn-use,G[i].w)) 但是他过了…………

2024/5/6 15:50
加载中...