这道题是很裸的最大流，和【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.
2023年5月18日 22:31
Canara Bank has thousands of branch and ATM locations throughout the country.We discuss, review, write about, and explain various products, services, technology, and other topics on our website, which is solely for learning and networkslog.com educational reasons. Having said that, we make every effort to keep the material up to date. There are various methods for checking Canara Bank balance. Find each method and Canara Bank balance check number for each type to obtain on demand... Canara Bank is one of India's largest banks, with over a million active customers.