这道题是很裸的最大流,和【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.