明显的二分图最大独立点权集
ans=总点权-最小割（最大流）
const dx:array[..] of longint=(,,-,);
dy:array[..] of longint=(,-,,);
inf=; type node=record
next,flow,point:longint;
end; var edge:array[..] of node;
d,p,cur,numh,h,pre:array[..] of longint;
num:array[..,..] of longint;
len,i,j,x,y,n,t,s,k:longint; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=z;
edge[len].next:=p[x];
p[x]:=len;
end; //省略sap begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=n*n+;
for i:= to n do
for j:= to n do
begin
read(x);
inc(k);
num[i,j]:=k;
if (i+j) mod = then
begin
add(,k,x);
add(k,,);
end
else begin
add(k,t,x);
add(t,k,);
end;
s:=s+x;
end; for i:= to n do
for j:= to n do
if (i+j) mod = then
begin
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if num[x,y]> then
begin
add(num[i,j],num[x,y],inf);
add(num[x,y],num[i,j],);
end;
end;
end;
writeln(s-sap);
end.