首页 > 代码库 > SCOI2007蜥蜴

SCOI2007蜥蜴

2024-07-09 13:18:56   231人阅读

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

1

HINT

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

题解：

网络流真是神奇！关键在构图！

点容量---拆点

无源无汇---附加源和汇

代码：（调了很长时间，结果竟然是insert写错了……）

  1 uses math;  2 const inf=maxlongint;  3 type node=record  4      go,next,v:longint;  5      end;  6 var e:array[0..50000] of node;  7     cnt,i,r,c,d,j,k,l,ans,tot,s,t:longint;  8     num:array[0..25,0..25,1..2] of longint;  9     first,h,q,cur:array[0..1000] of longint; 10     a:array[0..25,0..25] of char; 11     ch:char; 12 procedure ins(u,v,w:longint); 13  begin 14  inc(cnt); 15  e[cnt].go:=v;e[cnt].v:=w;e[cnt].next:=first[u];first[u]:=cnt; 16  end; 17 procedure insert(u,v,w:longint); 18  begin 19  ins(u,v,w);ins(v,u,0); 20  end; 21 function bfs:boolean; 22  var i,x,y,head,tail:longint; 23  begin 24  fillchar(h,sizeof(h),0); 25  head:=0;tail:=1;q[1]:=s;h[s]:=1; 26  while head<tail do 27   begin 28   inc(head); 29   x:=q[head]; 30   i:=first[x]; 31   while i<>0 do 32    begin 33     y:=e[i].go; 34     if (h[y]=0) and (e[i].v<>0) then 35      begin 36       h[y]:=h[x]+1; 37       inc(tail); 38       q[tail]:=y; 39      end; 40     i:=e[i].next; 41    end; 42   end; 43  exit(h[t]<>0); 44  end; 45 function dfs(x,f:longint):longint; 46  var used,tmp,i,y:longint; 47  begin 48  if x=t then exit(f); 49  tmp:=0;used:=0; 50  i:=cur[x]; 51  while i<>0 do 52   begin 53    y:=e[i].go; 54    if (h[y]=h[x]+1) and (e[i].v<>0)  then 55     begin 56     tmp:=dfs(y,min(f-used,e[i].v)); 57     dec(e[i].v,tmp); 58     inc(e[i xor 1].v,tmp); 59     if e[i].v<>0 then cur[x]:=i; 60     inc(used,tmp); 61     if used=f then exit(f); 62     end; 63    i:=e[i].next; 64    end; 65   if used=0 then h[x]:=-1; 66   exit(used); 67   end; 68 procedure dinic; 69  var i:longint; 70  begin 71  ans:=0; 72  while bfs do 73   begin 74    for i:=s to t do cur[i]:=first[i]; 75    inc(ans,dfs(s,inf)); 76   end; 77  end; 78 procedure init; 79  begin 80  readln(r,c,d); 81  s:=0;t:=2*r*c+1;cnt:=1; 82  for i:=1 to r do 83   for j:=1 to c do 84    begin 85     num[i,j,1]:=(i-1)*c+j; 86     num[i,j,2]:=(i-1)*c+j+r*c; 87    end; 88  for i:=1 to r do 89   begin 90    for j:=1 to c do read(a[i,j]); 91    readln; 92   end; 93  for i:=1 to r do 94   for j:=1 to c do 95    if a[i,j]<>‘0‘ then 96     begin 97      insert(num[i,j,1],num[i,j,2],ord(a[i,j])-48); 98      if (i-d<1) or (i+d>r) or (j-d<1) or (j+d>c)  then insert(num[i,j,2],t,inf) 99      else100       begin101      for k:=i-d to i+d do102       for l:=j-d to j+d do103        if sqr(abs(k-i))+sqr(abs(l-j))<=sqr(d) then insert(num[i,j,2],num[k,l,1],inf);104       end;105     end;106  tot:=0;107  for i:=1 to r do108   begin109    for j:=1 to c do110     begin111     read(ch);112     if ch<>‘.‘ then113      begin114       inc(tot);115       insert(s,num[i,j,1],1);116      end;117     end;118    readln;119   end;120  end;121 procedure main;122  begin123  dinic;124  writeln(tot-ans);125  end;126 begin127  init;128  main;129 end.
View Code

 

 


联系
我们