bzoj1066 [SCOI2007]蜥蜴

Description

　　在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃
到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石
柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不
变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同一个
石柱上。

Input

　　输入第一行为三个整数r，c，d，即地图的规模与最大跳跃距离。以下r行为石竹的初始状态，0表示没有石柱
，1~3表示石柱的初始高度。以下r行为蜥蜴位置，“L”表示蜥蜴，“.”表示没有蜥蜴。

Output

　　输出仅一行，包含一个整数，即无法逃离的蜥蜴总数的最小值。

Sample Input

5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

Sample Output

HINT

100%的数据满足：1<=r, c<=20, 1<=d<=4

网络流题目，建图的拆1个石柱为2个连上容量为高度的边没有想到。然后做的时候发现无向边得连两条有向边，再加上它们的反向边一共4条，不能用只连2条然后相互作为rev，我也不值得为什么，反正不这样就会WA一个点。

看了别的大神的博客。

传送门：http://www.cnblogs.com/qtyytq/p/5230616.html

  1 program rrr(input,output);
  2 const
  3   inf=123456789;
  4 type
  5   etype=record
  6      t,c,next,rev:longint;
  7   end;
  8 var
  9   e:array[0..400040]of etype;
 10   a,dep,cur:array[-440..440]of longint;
 11   x,y,z:array[0..440]of longint;
 12   q:array[0..880]of longint;
 13   r,c,d,i,j,cnt,tot,h,t,ans,n:longint;
 14   ma:array[0..22,0..22]of char;
 15   ch:char;
 16 function min(a,b:longint):longint;
 17 begin
 18    if a<b then exit(a) else exit(b);
 19 end;
 20 procedure ins(x,y,c:longint);
 21 begin
 22    inc(cnt);e[cnt].t:=y;e[cnt].c:=c;e[cnt].next:=a[x];a[x]:=cnt;
 23 end;
 24 procedure add(x,y,c:longint);
 25 begin
 26    ins(x,y,c);e[cnt].rev:=cnt+1;ins(y,x,0);e[cnt].rev:=cnt-1;
 27 end;
 28 procedure bfs;
 29 begin
 30    for i:=-tot to tot+1 do dep[i]:=-1;
 31    h:=0;t:=1;q[1]:=0;dep[0]:=0;
 32    while h<t do
 33       begin
 34          inc(h);i:=a[q[h]];
 35          while i<>0 do
 36             begin
 37                if (dep[e[i].t]=-1) and (e[i].c>0) then
 38                   begin
 39                      dep[e[i].t]:=dep[q[h]]+1;
 40                      inc(t);q[t]:=e[i].t;
 41                   end;
 42                i:=e[i].next;
 43             end;
 44       end;
 45 end;
 46 function dfs(k,f:longint):longint;
 47 var
 48   i,ans,r:longint;
 49 begin
 50    if (k=tot+1) or (f=0) then exit(f);
 51    ans:=0;i:=cur[k];
 52    while i<>0 do
 53       begin
 54          if (dep[e[i].t]=dep[k]+1) and (e[i].c>0) then
 55             begin
 56                r:=dfs(e[i].t,min(f,e[i].c));
 57                dec(e[i].c,r);inc(e[e[i].rev].c,r);
 58                dec(f,r);inc(ans,r);
 59                if f=0 then break;
 60             end;
 61          i:=e[i].next;cur[k]:=i;
 62       end;
 63    if f>0 then dep[k]:=-1;
 64    exit(ans);
 65 end;
 66 begin
 67    assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
 68    readln(r,c,d);
 69    fillchar(a,sizeof(a),0);cnt:=0;
 70    tot:=0;
 71    for i:=1 to r do
 72       begin
 73          for j:=1 to c do
 74             begin
 75                read(ch);if ch='0' then continue;
 76                inc(tot);x[tot]:=i;y[tot]:=j;val(ch,z[tot]);
 77                add(-tot,tot,z[tot]);
 78             end;
 79          readln;
 80       end;
 81    for i:=1 to r do begin for j:=1 to c do read(ma[i,j]);readln; end;
 82    n:=0;
 83    for i:=1 to tot do
 84       begin
 85          if ma[x[i],y[i]]='L' then begin add(0,-i,1);inc(n); end;
 86          if (x[i]<=d) or (y[i]<=d) or (r+1-x[i]<=d) or (c+1-y[i]<=d) then add(i,tot+1,inf);
 87          for j:=i+1 to tot do
 88             if sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(d) then
 89                begin add(i,-j,inf);add(j,-i,inf); end;
 90       end;
 91    ans:=0;
 92    while true do
 93       begin
 94          bfs;
 95          if dep[tot+1]=-1 then break;
 96          for i:=-tot to tot+1 do cur[i]:=a[i];
 97          ans:=ans+dfs(0,inf);
 98       end;
 99    write(n-ans);
100    close(input);close(output);
101 end.

优质内容筛选与推荐>>
1、文件处理
2、H5移动前端完美布局之padding
3、SSH 三大框架整合
4、Django的视图层简介
5、vue router mode模式在webpack 打包上线问题

0 │ 收藏 │ 举报