记录编号	141951	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]圈地计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-12-05 15:54:23	内存使用	0.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=10010,SIZEn=110,INF=0x7fffffff/2;
int N,S,T,sum;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
void addedge(int from,int to,int cap){
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
bool vis[SIZEN]={0};
int depth[SIZEN]={0};
queue<int> Q;
bool BFS(void){
	memset(vis,0,sizeof(vis));
	memset(depth,0,sizeof(depth));
	vis[S]=true;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			EDGE &e=edges[c[x][i]];
			if(e.flow<e.cap){
				if(!vis[e.to]){
					vis[e.to]=true;
					depth[e.to]=depth[x]+1;
					Q.push(e.to);
				}
			}
		}
	}
	return vis[T];
}
int cur[SIZEN]={0};
int DFS(int x,int a){
	if(x==T||!a) return a;
	int ans=0;
	for(int &i=cur[x];i<c[x].size();i++){
		EDGE &e=edges[c[x][i]];
		if(e.flow<e.cap&&depth[e.to]==depth[x]+1){
			int cf=DFS(e.to,min(a,e.cap-e.flow));
			if(cf){
				a-=cf;ans+=cf;
				e.flow+=cf;edges[c[x][i]^1].flow-=cf;
			}
			if(!a) break;
		}
	}
	if(!ans) depth[x]=-1;
	return ans;
}
int Dinic(void){
	int ans=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		ans+=DFS(S,INF);
	}
	return ans;
}
int n,m;
int hash(int i,int j){
	return i*m+j;
}
int A[SIZEn][SIZEn],B[SIZEn][SIZEn],C[SIZEn][SIZEn];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void makegraph(void){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if((i+j)&1){//最小割选中的是放弃的边,因此当相邻格同为A或B时才会放弃中间的增值
				addedge(S,hash(i,j),A[i][j]);
				addedge(hash(i,j),T,B[i][j]);
			}
			else{
				addedge(S,hash(i,j),B[i][j]);
				addedge(hash(i,j),T,A[i][j]);
			}
			sum+=A[i][j]+B[i][j];
			for(int d=0;d<4;d++){
				int i1=i+dx[d],j1=j+dy[d];
				if(0<=i1&&i1<n&&0<=j1&&j1<m){
					addedge(hash(i,j),hash(i1,j1),C[i][j]+C[i1][j1]);//这是由于割边只算从S到T的
					sum+=C[i][j];
				}
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	N=n*m+1;S=N-1,T=N;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&A[i][j]);
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&B[i][j]);
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&C[i][j]);
}
int main(){
	freopen("nt2011_land.in","r",stdin);
	freopen("nt2011_land.out","w",stdout);
	read();
	makegraph();
	printf("%d\n",sum-Dinic());
	return 0;
}