比较裸的最小割
注意狼和羊的领地可以通过空地相连
const inf=;
dx:array[..] of integer=(,,,-);
dy:array[..] of integer=(-,,,); type node=record
next,point,flow:longint;
end; var edge:array[..] of node;
a,num:array[..,..] of longint;
p,cur,h,numh,pre:array[..] of longint;
n,m,x,y,len,i,j,t,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);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var s,u,i,j,neck,q,tmp:longint;
begin
u:=;
numh[]:=t+;
sap:=;
while h[]<t+ do
begin
if u=t then
begin
i:=;
neck:=inf;
while i<>t do
begin
j:=cur[i];
if neck>edge[j].flow then
begin
neck:=edge[j].flow;
s:=i;
end;
i:=edge[j].point;
end;
i:=;
while i<>t do
begin
j:=cur[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
i:=edge[j].point;
end;
u:=s;
sap:=sap+neck;
end;
q:=-;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
q:=i;
break;
end;
i:=edge[i].next;
end;
if q<>- then
begin
cur[u]:=q;
pre[j]:=u;
u:=j;
end
else begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t+;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then tmp:=min(tmp,h[j]);
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then u:=pre[u];
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
for i:= to n do
for j:= to m do
begin
read(a[i,j]);
inc(t);
num[i,j]:=t;
end;
inc(t);
for i:= to n do
for j:= to m do
begin
if a[i,j]= then
begin
add(,num[i,j],inf);
add(num[i,j],,);
end
else if a[i,j]= then
begin
add(num[i,j],t,inf);
add(t,num[i,j],);
end;
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if (x>) and (x<=n) and (y>) and (y<=m) then
begin
if (a[i,j]=) and (a[x,y]<>) then
begin
add(num[i,j],num[x,y],);
add(num[x,y],num[i,j],);
end
else if (a[i,j]=) then
begin
add(num[i,j],num[x,y],);
add(num[x,y],num[i,j],);
end;
end;
end;
end;
writeln(sap);
end.