传送门

很魔性的一道题。

显然应该根据这个图应该划分成二分图的性质，S点集和T点集分别代表文理科，然后求最小割即可。

如果忽略same_art和same_science的话，建图很显然。所以在这个基础上添加一些东西。

对于每个点，拆为三个点，第一个点正常处理，第二个点和第三个点分别代表same_science和same_art。

以S点集为例。分别连两条边：$S \rightarrow same_{science}$和$same_{science} \rightarrow V_{nxt}$，容量分别为same_science和$\infty$。

为什么这样处理？

首先比如说相邻的五个点都是science，其中有一个要割为art，显然这些点的same_science也要一块割掉，这时候选了art的点还有一条边连着S，即same_art，然后就会被割掉。这样就很好的解决了问题。

//BZOJ 3894//by Cydiater//2017.1.16#include <iostream>#include <queue>#include <map>#include <ctime>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cstdio>#include <iomanip>#include <cmath>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)const int MAXN=1e3+5;const int oo=0x3f3f3f3f;const int dx[5]={1,0,-1,0,0};const int dy[5]={0,1,0,-1,0};inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int art[MAXN][MAXN],same_art[MAXN][MAXN],science[MAXN][MAXN],same_science[MAXN][MAXN];int LINK[MAXN<<10],len=0,N,M,ID[MAXN][MAXN][3],level[MAXN<<10],cnt=0,S,T,ans=0,q[MAXN<<11],head,tail;struct edge{	int y,next,flow,reverse;}e[MAXN<<11];namespace solution{	inline void insert(int x,int y,int flow,int delta){		e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].flow=flow;e[len].reverse=len+delta;	}	void Prepare(){		N=read();M=read();		up(i,1,N)up(j,1,M)ans+=(art[i][j]=read());		up(i,1,N)up(j,1,M)ans+=(science[i][j]=read());		up(i,1,N)up(j,1,M)ans+=(same_art[i][j]=read());		up(i,1,N)up(j,1,M)ans+=(same_science[i][j]=read());		up(i,1,N)up(j,1,M)up(k,0,2)ID[i][j][k]=++cnt;		S=++cnt;T=++cnt;		up(i,1,N)up(j,1,M){			//art			insert(S,ID[i][j][0],art[i][j],1);			insert(ID[i][j][0],S,0,-1);			//science			insert(ID[i][j][0],T,science[i][j],1);			insert(T,ID[i][j][0],0,-1);			//same_art			insert(S,ID[i][j][1],same_art[i][j],1);			insert(ID[i][j][1],S,0,-1);			up(k,0,4){				int tx=i+dx[k],ty=j+dy[k];				if(tx>=1&&tx<=N&&ty>=1&&ty<=M){					insert(ID[i][j][1],ID[tx][ty][0],oo,1);					insert(ID[tx][ty][0],ID[i][j][1],0,-1);				}			}			//same_science			insert(ID[i][j][2],T,same_science[i][j],1);			insert(T,ID[i][j][2],0,-1);			up(k,0,4){				int tx=i+dx[k],ty=j+dy[k];				if(tx>=1&&tx<=N&&ty>=1&&ty<=M){					insert(ID[tx][ty][0],ID[i][j][2],oo,1);					insert(ID[i][j][2],ID[tx][ty][0],0,-1);				}			}		}	}	bool makelevel(){		head=1;tail=0;q[++tail]=S;		memset(level,-1,sizeof(level));		level[S]=0;		for(;head<=tail;head++){			int node=q[head];			Auto(i,node)if(level[e[i].y]==-1&&e[i].flow){				level[e[i].y]=level[node]+1;				q[++tail]=e[i].y;			}		}		return level[T]!=-1;	}	int addflow(int node,int flow){		if(node==T)	return flow;		int d=0,maxflow=0;		Auto(i,node)if(level[e[i].y]==level[node]+1&&e[i].flow)			if(d=addflow(e[i].y,min(e[i].flow,flow-maxflow))){				maxflow+=d;				e[i].flow-=d;				e[e[i].reverse].flow+=d;			}		if(maxflow<=0)level[node]=-1;		return maxflow;	}	void Dinic(){		int d;		while(makelevel())			while(d=addflow(S,oo))				ans-=d;	}	void Solve(){		Dinic();		printf("%d\n",ans);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

BZOJ3894: 文理分科