网络流求调
查看原帖
网络流求调
429499
isletfall楼主2023/12/15 15:21

WA on Test 4,答案2输出1

#include<bits/stdc++.h>
using namespace std;
using namespace std;
const int maxn=2e5+7;
int n,p,q,cnt=1,max_flow,s,t;
int head[maxn],dpt[maxn],cur[maxn];
struct node{
	int v,w,nxt;	
}e[maxn];
void add(int x,int y,int z){
	e[++cnt].v=y;
	e[cnt].w=z;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
bool bfs(){
	queue<int>q;
	memset(dpt,0,sizeof(dpt));
	dpt[s]=1;
	q.push(s);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=head[now];i;i=e[i].nxt){
			int y=e[i].v;
			if(e[i].w&&dpt[y]==0){
				q.push(y);
				dpt[y]=dpt[now]+1;
				if(y==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,int flow){
	if(x==t)return flow;
	int res=flow,k;
	for(int i=cur[x];i&&res;i=e[i].nxt){
		int y=e[i].v;
		cur[x]=i;
		if(e[i].w&&dpt[y]==dpt[x]+1){
			k=dfs(y,min(e[i].w,res));
			if(k==0)dpt[y]=0;
			e[i].w-=k;
			e[i^1].w+=k;
			res-=k;
		}
	}
	return flow-res;
}
int main(){
	cin>>n>>p>>q;
	t=p+q+n+n+1;
	for(int i=1;i<=p;i++){
		add(s,i,1);
		add(i,s,0);
	}
	for(int i=1;i<=q;i++){
		add(p+n+n+i,t,1);
		add(t,p+n+n+i,0);
	}
	for(int i=1;i<=n;i++){
		add(p+i,p+n+i,1);
		add(p+n+i,p+i,0);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			int x;
			cin>>x;
			if(x==1)
			add(j,p+i,1),add(p+i,j,0);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=q;j++){
			int x;
			cin>>x;
			if(x==1)
			add(p+n+i,p+n+n+j,1);
			add(p+n+n+j,p+n+i,0);
		}
	}
	int flow=0;
	while(bfs()){
		for(int i=0;i<=t;i++)
		cur[i]=head[i];
		while(flow=dfs(s,1<<29))max_flow+=flow;
	}
	cout<<max_flow;
	return 0;
}
2023/12/15 15:21
加载中...