program flow9;
const maxn=500;
var
g,a:array[0..maxn,0..maxn]of longint;
que,d:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
n,m:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function bfs(s,t:longint):boolean;
var i,u,l,r:longint;
begin
fillchar(que,sizeof(que),0);
fillchar(d,sizeof(d),0);
fillchar(v,sizeof(v),false);
l:=0;r:=1;que[l]:=s;v[s]:=true;
while l<r do
begin
u:=que[l];
for i:=0 to n*m+1 do
if (g[u][i]>0)and(not v[i]) then
begin
que[r]:=i;
inc(r);
v[i]:=true;
d[i]:=d[u]+1;
end;
inc(l);
end;
exit(v[t]);
end;
function dfs(p,a,t:longint):longint;
var f,flow,i:longint;
begin
if (p=t)or(a=0) then exit(a);
flow:=0;
for i:=0 to n*m+1 do
if (g[p][i]>0)and(d[i]=d[p]+1) then
begin
f:=dfs(i,min(a,g[p][i]),t);
if f=0 then continue;
inc(flow,f);
inc(g[i][p],f);
dec(g[p][i],f);
dec(a,f);
if a=0 then break;
end;
exit(flow);
end;
function dinic(s,t:longint):longint;
var ans:longint;
begin
ans:=0;
while bfs(s,t) do
ans:=ans+dfs(s,maxlongint,t);
exit(ans);
end;
procedure init;
var i,j,ans,tot:longint;
begin
read(n,m);
fillchar(g,sizeof(g),255);
tot:=0;
for i:=1 to n do
for j:=1 to m do
begin
read(a[i][j]);
tot:=tot+a[i][j];
end;
for i:=1 to n do
for j:=1 to m do
if (i+j)and 1=0 then
begin
g[0][(i-1)*m+j]:=a[i][j];
g[(i-1)*m+j][0]:=0;
if i>1 then
begin
g[(i-1)*m+j][(i-2)*m+j]:=maxlongint;
g[(i-2)*m+j][(i-1)*m+j]:=0;
end;
if i<n then
begin
g[(i-1)*m+j][i*m+j]:=maxlongint;
g[i*m+j][(i-1)*m+j]:=0;
end;
if j>1 then
begin
g[(i-1)*m+j][(i-1)*m+j-1]:=maxlongint;
g[(i-1)*m+j-1][(i-1)*m+j]:=0;
end;
if j<m then
begin
g[(i-1)*m+j][(i-1)*m+j+1]:=maxlongint;
g[(i-1)*m+j+1][(i-1)*m+j]:=0;
end;
end
else
begin
g[(i-1)*m+j][n*m+1]:=a[i][j];
g[n*m+1][(i-1)*m+j]:=0;
end;
ans:=dinic(0,n*m+1);
ans:=tot-ans;
write(ans);
end;
begin
init;
end.
评论