[数据结构与算法]文理分科 题解

题目链接

解法

我们考虑将题目转化，求最少的不能取的价值，然后考虑在每5个相邻的人中，如有一人选文科，那么全选理科的价值就取不到，如有一人选理科，那么全选文科的价值就取不到，故可以建下面这张图

没边权的就是inf

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,T,qg;
int xf[50005],v[500005],ne[500005],h[50005],val[500005],cur[50005],cnt,nn,ans,sum;
int ex[5]={0,1,0,-1,0},ey[5]={1,0,-1,0,0};
bool pd(int x,int y){
	return x<=n&&y<=m&&x>=1&&y>=1;
}
void add(int x,int y,int z){
	v[++cnt]=y;
	ne[cnt]=h[x];
	val[cnt]=z;
	h[x]=cnt;
}
bool bfs(){
	memset(xf,0,sizeof xf);
	for(int i=1;i<=nn;i++){
		cur[i]=h[i];
	}
	queue<int>q;
	xf[nn-1]=1;
	q.push(nn-1);
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=h[x];i;i=ne[i]){
			if(val[i]&&xf[v[i]]==0){
				xf[v[i]]=xf[x]+1;
				if(xf[nn])return 1;
				q.push(v[i]);
			}
		}
	}
	return 0;
}
int dfs(int x,int y){
	if(x==nn||y==0)return y;
	int rp=0;
	for(int i=cur[x];i;i=ne[i]){
		cur[x]=i;
		if(xf[v[i]]==xf[x]+1&&val[i]){
			int kk=dfs(v[i],min(y-rp,val[i]));
			rp+=kk;
			val[i]-=kk;
			val[i^1]+=kk;
		}
	}
	return rp;
}
int xff(int x,int y){
	return x*m-m+y;
}
int main(){
	scanf("%d%d",&n,&m);
	cnt=1;
	nn=3*n*m+2;
	for(int i=1;i<=n;i++){
		for(int j=1,u;j<=m;j++){
			scanf("%d",&u);
			add(nn-1,xff(i,j),u);
			add(xff(i,j),nn-1,0);
			sum+=u;
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1,u;j<=m;j++){
			scanf("%d",&u);
			add(xff(i,j),nn,u);
			add(nn,xff(i,j),0);
			sum+=u;
		} 
	}
	for(int i=1;i<=n;i++){
		for(int j=1,u;j<=m;j++){
			scanf("%d",&u);
			for(int l=0;l<5;l++){
				if(pd(i+ex[l],j+ey[l])){
					add(xff(i,j)+n*m,xff(i+ex[l],j+ey[l]),0x3f3f3f3f);
					add(xff(i+ex[l],j+ey[l]),xff(i,j)+n*m,0);
				}
			}
			add(nn-1,xff(i,j)+n*m,u);
			add(xff(i,j)+n*m,nn-1,0);
			sum+=u;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1,u;j<=m;j++){
			scanf("%d",&u);
			for(int l=0;l<5;l++){
				if(pd(i+ex[l],j+ey[l])){
					add(xff(i+ex[l],j+ey[l]),xff(i,j)+2*n*m,0x3f3f3f3f);
					add(xff(i,j)+2*n*m,xff(i+ex[l],j+ey[l]),0);
				}
			}
			add(xff(i,j)+2*n*m,nn,u);
			add(nn,xff(i,j)+2*n*m,0);
			sum+=u;
		}
	}
	while(bfs())ans+=dfs(nn-1,0x3f3f3f3f);
	printf("%d\n",sum-ans);
}