60pts求助
查看原帖
60pts求助
285617
黑影洞人楼主2022/8/13 10:41
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define N 114514
#define inf 2147483647
#define int long long
using namespace std;
int n,p,q,head[N],to[N],nxt[N],val[N],tot=1,s,t,d[N]; 
void add(int u,int v,int w){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	val[tot]=w;
}
bool bfs(){
	queue<int>q;
	q.push(s);
	memset(d,-1,sizeof(d));
	d[s]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			if(!val[i])continue;
			int y=to[i];
			if(d[y]==-1){
				d[y]=d[x]+1;
				if(y==t)return 1;
				q.push(y);
			}
		}
	}
	return 0;
}
int dfs(int x,int a){
	if(!a||x==t)return a;
	int res=a;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(val[i]&&d[y]==d[x]+1){
			int tmp=dfs(y,min(val[i],res));
			res-=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			if(res<=0)return a;
		}
	}
	if(res==a)d[x]=-1;
	return a-res;
}
int dinic(){
	int flow=0;
	while(bfs())flow+=dfs(s,inf);
	return flow;
}
signed main(){
	scanf("%lld%lld%lld",&n,&p,&q);
	s=0,t=2*n+p+q+1;
	for(int i=1;i<=p;i++){
		add(s,2*n+i,1);
		add(n+i,s,0);
	}
	for(int i=1;i<=q;i++){
		add(2*n+i+p,t,1);
		add(t,2*n+i+p,0);
	}
	for(int i=1;i<=n;i++){
		add(i,i+n,inf);
		add(i+n,i,0);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			int d;
			scanf("%lld",&d);
			if(d){
				add(2*n+j,i,1);
				add(i,2*n+j,0);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=q;j++){
			int d;
			scanf("%lld",&d);
			if(d){
				add(i+n,2*n+j+p,1);
				add(2*n+j+p,i+n,0);
			}
		}
	}
	printf("%lld",dinic());
	return 0;
}



2022/8/13 10:41
加载中...