题目描述
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）

小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。

如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加same_art[i][j]的满意值。

如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加same_science[i][j]的满意值。

小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

输入格式
第一行为两个正整数：n，m

接下来n行m个整数，表示art[i][j]；

接下来n行m个整数．表示science[i][j]；

接下来n行m个整数，表示same_art[i][j]；

接下来n行m个整数，表示same_science[i][j]；

输出格式
输出为一个整数，表示最大的满意值之和

输入输出样例
输入 #1复制
3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4
输出 #1复制
152
说明/提示
样例说明
1表示选择文科，0表示选择理科，方案如下：

1 0 0 1

0 1 0 0

1 0 0 0

数据范围
N,M<=100,读入数据均<=500

很明显的一道集合分割，对于每个点非黑即白，于是我们可以采用，最小割。

对于每个点的两种状态，我们分别用S连向点，和点连向T。对于点和附近的点的共同收益，我们建立新的节点，让S连向新的节点，流量为增加的收益，新的节点连向相连的点和本身。对于连向T的同理。

这样不同的最小割就代表了不同的方案，答案就是总的值，减去最小割。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=100010,M=1000010;
const int dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0};
int n,m,s,t,base,h[N],res;
int head[N],nex[M],to[M],w[M],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
inline int id(int x,int y){
	return m*(x-1)+y;
}
int bfs(){
	queue<int> q;	q.push(s);	memset(h,0,sizeof h);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!h[to[i]]&&w[i]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(h[to[i]]==h[x]+1&&w[i]){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	fl+=mi;	f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;	
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
signed main(){
	cin>>n>>m;	base=n*m;	s=0;	t=base*3+10;	int x;
	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	cin>>x,add(s,id(i,j),x),res+=x;
	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)	cin>>x,add(id(i,j),t,x),res+=x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;	add(s,id(i,j)+base,x);	res+=x;
			for(int k=0;k<5;k++){
				int tx=i+dx[k];	int ty=j+dy[k];
				if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
					add(id(i,j)+base,id(tx,ty),inf);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;	add(id(i,j)+base*2,t,x);	res+=x;
			for(int k=0;k<5;k++){
				int tx=i+dx[k];	int ty=j+dy[k];
				if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
					add(id(tx,ty),id(i,j)+base*2,inf);
				}
			}
		}
	}
	cout<<res-dinic()<<endl;
	return 0;
}