这算是最小割中比较难的吧
看到选取显然最小割
看到上下左右四个点我感觉肯定和染色相关
注意每个点的收益获得条件是[或]，因此我们考虑拆点i', i，分别表示通过四周控制和控制本身的代价
连边s-->i 流量为选择该点的代价； i-->i' 流量为该点的收益； i'到上下左右的j，流量为正无穷，表示另一个条件
这样，要获得收益便一定要割断一边，就满足了或的性质
注意，另一种颜色的连边与这种颜色相反，由于染色可以得到二分图
所以另一种颜色的连边反过来建即可
const inf=;
dx:array[..] of longint=(,,-,);
dy:array[..] of longint=(,-,,); type node=record
po,next,flow:longint;
end; var e:array[..] of node;
numh,h,cur,p,pre,d:array[..] of longint;
a:array[..,..] of longint;
ans,i,j,x,y,len,t,n,m,k:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
e[len].po:=y;
e[len].flow:=f;
e[len].next:=p[x];
p[x]:=len;
end; procedure build(x,y,f:longint);
begin
add(x,y,f);
add(y,x,);
end; function sap:longint;
var i,j,u,neck,tmp,q:longint;
begin
for i:= to t do
cur[i]:=p[i];
sap:=;
u:=;
neck:=inf;
numh[]:=t+;
while h[]<t+ do
begin
i:=cur[u];
d[u]:=neck;
while i<>- do
begin
j:=e[i].po;
if (e[i].flow>) and (h[u]=h[j]+) then
begin
neck:=min(neck,e[i].flow);
pre[j]:=u;
cur[u]:=i;
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(e[j].flow,neck);
inc(e[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=e[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t;
q:=-;
i:=p[u];
while i<>- do
begin
j:=e[i].po;
if e[i].flow> then
if h[j]<tmp then
begin
tmp:=h[j];
q:=i;
end;
i:=e[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
t:=*n*m+;
for i:= to n do
for j:= to m do
begin
read(x);
inc(k); a[i,j]:=k;
if (i+j) mod = then build(,a[i,j],x)
else build(a[i,j],t,x);
end; for i:= to n do
for j:= to m do
begin
read(x);
ans:=ans+x;
if (i+j) mod = then build(a[i,j],a[i,j]+n*m,x)
else build(a[i,j]+n*m,a[i,j],x);
end; for i:= to n do
for j:= to m do
begin
if (i+j) mod = then
begin
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if (x<=) or (x>n) or (y<=) or (y>m) then continue;
build(a[i,j]+n*m,a[x,y],inf);
end;
end
else begin
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if (x<=) or (x>n) or (y<=) or (y>m) then continue;
build(a[x,y],a[i,j]+n*m,inf);
end;
end;
end; writeln(ans-sap);
end.