记录编号	427641	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]圈地计划	最终得分	100
用户昵称	YPZ_979	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-07-22 19:16:50	内存使用	5.03 MiB

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iomanip>
#include<cstring>
#define inf 1<<29
#define ll long long
#define db double
#define re register
#define il inline
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int N=110,M=N*N*12;
struct Edge{
  int to,net,flow,cap;
}e[M*2];
int head[N*N],num_e,n,m;
int s,t;
int id[N][N];
int k[N][N],bk[N][N],C[N][N];
inline int gi() {
  re int res=0,f=1;re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') f=-1,ch=getchar();
  while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
  return res*f;
}
int num;
il void add(int x,int y,int c){
  e[++num_e].to=y,e[num_e].cap=c,e[num_e].net=head[x],head[x]=num_e;
}
void init(){
  n=gi(),m=gi();
  rep(i,1,n)
    rep(j,1,m)
    k[i][j]=gi();
  rep(i,1,n)
    rep(j,1,m)
    bk[i][j]=gi();
  rep(i,1,n)
    rep(j,1,m)
    C[i][j]=gi();
  rep(i,1,n)
    rep(j,1,m)
    id[i][j]=++num;
}
bool hb[N][N];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int lev[N*N];
il bool bfs(){
  queue<int> q;
  memset(lev,0,sizeof(lev));
  q.push(s);lev[s]=1;
  while(!q.empty()){
    re int u=q.front();q.pop();
    for(int i=head[u];i!=-1;i=e[i].net){
      int to=e[i].to;
      if(!lev[to]&&e[i].cap>e[i].flow){
	lev[to]=lev[u]+1;
	q.push(to);
	if(lev[t]) return 1;
      }
    }
  }
  return 0;
}
int dfs(int x,int f){
  if(x==t) return f;
  int tag=0;
  for(int i=head[x];i!=-1;i=e[i].net){
    int to=e[i].to;
    if(lev[to]==lev[x]+1&&e[i].cap>e[i].flow){
      int c=dfs(to,min(f-tag,e[i].cap-e[i].flow));
      e[i].flow+=c;
      e[i^1].flow-=c;
      tag+=c;
      if(tag==f) break;
    }
  }
  if(!tag) lev[x]=0;
  return tag;
}
int Dinic(){
  re int flow=0;
  while(bfs())
    flow+=dfs(s,inf);
  return flow;
}
void wll(){
  memset(head,-1,sizeof(head)),num_e=-1;
  s=0;t=num+1;
  int sum=0;
  rep(i,1,n)
    rep(j,1,m) {
    if(i%2==j%2){
      add(s,id[i][j],k[i][j]),add(id[i][j],s,0);
      add(id[i][j],t,bk[i][j]),add(t,id[i][j],0);
    }
    else {
      add(s,id[i][j],bk[i][j]),add(id[i][j],s,0);
      add(id[i][j],t,k[i][j]),add(t,id[i][j],0);
    }
    sum+=k[i][j]+bk[i][j];
    for(re int h=0;h<4;h++){
      re int u=i+dx[h],v=j+dy[h];
      if(u>=1&&u<=n&&v>=1&&v<=m){
	add(id[i][j],id[u][v],C[i][j]+C[u][v]),add(id[u][v],id[i][j],0);
	sum+=C[i][j];
      }
    }
  }
  printf("%d",sum-Dinic());
}
int main(){
  file("nt2011_land");
  init();
  wll();
  return 0;
}