这道题是很裸的最大流，和【BZOJ1189】紧急疏散很像，不过这道题不用按照时间拆点，需要对于每个柱子拆点，在同一个柱子的两个点间连一条流量为柱子可以通过蜥蜴数的边（即高度），然后对于这张图做最大流即可。
program p1066;
const
maxn=100000000;
type
bian=record
next,point,f:longint;
end;
var
p,dst:array[0..40000] of longint;
w:array[1..50,1..50] of longint;
x:array[1..400000] of longint;
pd:array[0..40000] of boolean;
b:array[0..40000] of bian;
len,tot,x1,x2,y1,y2,i,j,n,m,d:longint;
ch:char;
procedure ade(k1,k2,k3:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
p[k1]:=len;
end;
procedure add(k1,k2,k3:longint);
begin
ade(k1,k2,k3);
ade(k2,k1,0);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function bfs:boolean;
var
k1,k2,k3,now,head,i,j:longint;
begin
fillchar(pd,sizeof(pd),false);
pd[0]:=true; head:=1; now:=0; x[1]:=0; dst[0]:=0;
while now<head do begin
inc(now);
i:=p[x[now]];
while i>-1 do begin
k1:=b[i].point;
{writeln(k1,' ',b[i].f);
readln;}
if (pd[k1]=false) and (b[i].f>0) then begin
pd[k1]:=true;
dst[k1]:=dst[x[now]]+1;
if k1=n then exit(true);
inc(head);
x[head]:=k1;
end;
i:=b[i].next;
end;
end;
exit(pd[n]);
end;
function change(k1,k2:longint):longint;
var
now,i,j,k:longint;
begin
if (k1=n) or (k2=0) then exit(k2);
now:=p[k1];
j:=0;
while now>-1 do begin
i:=b[now].point;
if (b[now].f>0) and (dst[k1]=dst[i]-1) then begin
k:=change(i,min(b[now].f,k2));
k2:=k2-k;
j:=j+k;
b[now].f:=b[now].f-k;
inc(b[now xor 1].f,k);
if k2=0 then break;
end;
now:=b[now].next;
end;
if j=0 then dst[k1]:=-1;
exit(j);
end;
function dinic:longint;
var
num:longint;
begin
num:=0;
while bfs=true do
num:=num+change(0,maxn);
exit(num);
end;
begin
len:=-1;
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
readln(n,m,d);
for i:=1 to n do begin
for j:=1 to m do begin
read(ch);
w[i,j]:=ord(ch)-ord('0');
if (i<=d) or (j<=d) or (i>=n-d+1) or (j>=m-d+1) then add(i*m-m+j+n*m,n*m*2+1,maxn);
end;
readln;
end;
for x1:=1 to n do
for y1:=1 to m do
for x2:=1 to n do
for y2:=1 to m do
if ((x1<>x2) or (y1<>y2)) and (sqrt(sqr(x1-x2)+sqr(y1-y2))<=d) then
add(x1*m-m+y1+n*m,x2*m-m+y2,maxn);
tot:=0;
for i:=1 to n do begin
for j:=1 to m do begin
read(ch);
if ch='L' then begin
dec(w[i,j]);
add(0,i*m-m+j+n*m,1);
inc(tot);
end;
add(i*m-m+j,i*m-m+j+n*m,w[i,j]);
end;
readln;
end;
n:=n*m*2+1;
writeln(tot-dinic);
end.
评论 (0)
