首页 > 代码库 > SCOI2007蜥蜴
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..
........
........
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.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。