国家集训队作业0060研究报告

1、IOI2003 中国国家集训队难题0060活动市复旦大学附属中学【题目大意】农田是一个 n x m（n,m30）的矩阵。农田的 k（k200）个小方格内是喷水龙头，可以朝东西南北四个方向直线喷洒非负整数距离的水即灌溉那里的小方格（四个方向的喷洒距离可以不同）。同一小方格要么是喷水龙头安放处，要么恰好属于一个喷水龙头的灌溉范围。灌溉一个小方格需要一个的水量，而每个喷水龙头有各自不同的水量。每个喷水龙头的水必须恰好用完。现在给你农田的大小和每个喷水龙头的位置及水量，请你设计一整套灌溉系统。【解决情况】采用的算法仍然要依靠搜索，因此复杂度是指数阶的，具体估计时间复杂度仍十分，时间复杂度上限难以确定，

2、下限为 O(4*n*m)。从实际效果看来，算法对于大量的随机数据表现良好（已经测试了 200 多个随机数据）。【算法梗概】算法的主要将能够直接确定的方格全部确定，然后在此基础上进行搜索，由于方格与喷水龙头之间的制约关系比较强，因此可以直接确定许多方格，在此基础上进行搜索效率比较高。当然也有例外，例如整个 n*m 的方格呈棋盘布局，但是这样的情况布局情况非常之多，搜索可以很快找到一个可行方案。【正文】1解题的几种思路本题的问题模型建立在 n*m 方格上，问题描述的形式与一些可以用经典模型解决的题目似曾相识。但其求解的要求却有不同，本题要求的是找到一种覆盖所有方格的可行方案，而往往接触的题目则是求

3、最优解。但题目描述变更一下，允许方格重复灌溉，求最大灌溉面积的方案。因此仍可视为求最优方案，那么这样的题目往往使人有一种套用经典算法的冲动。那么让来看一下一些经典模型是否能对本题的解决有所帮助。那么我在下面的表格中列举了一部份想法。其中可能可以实现的也只有基于猜想的动态规划(2)及搜索算法，为了进一步认识本题的内在关系，对样例进行分析。2样例分析口说无凭，到底动态规划是否可行，搜索效率高不高，先让来分析一下样例：5 5655 2 25 4 2注：白色的格子为未灌溉的格子，数字表示喷头的，括号内的数字表示所剩水量3(4)6(2)1(2)4(5)5(2)2(4)模型分类算法存在可能的帮助存在的图论

4、最短路、生成树无任何直接关联似乎不存在可借鉴之处模型差别较 以进行联系匹配确定各个方向上的水量可能可以对特殊情况进行求解很难将每个方格只灌溉一次的条件联系起来，即很难保证求得可行方案网络流水量的限制视为流量的限制，可以将 k 个喷水龙头视为 k 个源或以在求得初步方案的基础上进行调整，使灌溉的方向为一直线很难将灌溉的方法为向四个方向进行连续的灌溉与模型进行有效的结合动态规划动态规划（1）联想到 NOI2001的 兵阵地小规模的情况可能可以进行求解分割线的状态量过于庞大，可以达到 minnm, mn动态规划（2）基于一种猜想，如果整个 n*m 的网格可以用某一条 直线分割成两半，且两半都能够分

5、别找到灌溉方案，则即可解决对某些特殊的情况可能可以进行求解由于猜想的要求是用直线进行分割，那相当于网格上有一条“三八”线，这样的要求对于灌溉方案限制过于严格，很难找到可行解贪心贪心无任何直接关联或以贪心得到 某种可行方案由于最终解的限制很严格，因此直接使用贪心求解，可能性过于渺茫搜索搜索这类题目最后的选择一定能够搜索得到可行解时间效率是一个主要的问题仔细观察样例中的一些方格，溉，这是否也是一个解题的关键呢？可以发现有些方格只可能由唯一的一个喷水龙头灌对样例进行进一步的尝试。来看一下，上面这个例子，哪些方格可以直接确定，分别用颜色表示出来。观察(1,2)的格子，发现其北面为 1 号喷水龙头，而东

6、面的 5 号喷水龙头水量不足以喷到(1,2)，因此可以确定(1,2)由 1 号喷水龙头喷到，同理可以确定(1,4)。位置为(1,1)的格子，只能由 2 号喷水龙头喷到，同样(1,5)也只能由 3 号喷水龙头喷到，位置为(4,1)的格子（位于 2 号喷水龙头东面），只能由 2 号喷水龙头喷到，同样(4,5)只能由3 号喷水龙头喷到。再观察(2,2)的格子（位于 2 号喷水龙头北面），虽然三面都有喷水龙头（南面为 2 号，东面为 5 号，北面为 3 号），但是由于东面及北面的水量不够（至少 3 才能喷到），因此只能由 2 号喷水龙头喷到，同理可以确定(2,4)。显然(2,3)只能由 4 号喷到，(

7、5,1)，(4,2)只能由 5 号喷到，(5,5)，(4,4)只能由 6 号喷到。此时只剩下 4 号喷水龙头，可以确定剩下的格子了。3初步的设想发现这个例子只有唯一的一个可行方案，但令根本不需要借助搜索，直接确定即可。惊奇的是解决这样一个样例3(0)6(0)1(0)4(0)5(0)2(0)3(0)6(0)1(0)4(4)5(0)2(0)3(0)6(2)1(0)4(5)5(2)2(0)3(1)6(2)1(0)4(5)5(2)2(1)3(4)6(2)1(0)4(5)5(2)2(4)同时点直接的导致因此也发现这个例子，也不可能找到一条分割线能够将整个网格分成两部分。这一否定了动态规划的猜想。可以发现

8、喷水龙头比较稀疏时，可以直接确定大部分格子的灌溉方案，在此基础上进行搜索效率会比较高。而当喷水龙头的数量非常密集以至于不可能直接确定任何一个格子时，则解的数目也应当非常之多的。搜索应当能够很快地能找到一个可行解。那么有了初步的想法，就要开始实际操作。在这样一个网格上找到可以直接确定的方格需要考虑到哪些方面，实现哪些操作呢？一个方格能否被一个喷水龙头灌溉取决于两个方面，一是喷水龙头是否有足够的水量，另一个是灌溉的路线上是否会遇到直线上有已被其他喷水龙头或被其他喷水龙头灌溉的方格）。如果一个方格只可能被一个喷水龙头灌溉，就可以直接确定此方格的灌溉方案。那么须判断一个方格可以由几个方向进行灌溉。为了

9、实现上述判断，每次必须从一个方格的四个方向出发找到最近的喷水龙头，再进行判断此喷水龙头是否可以灌溉此方格（是否在灌溉路线上受阻）。这样做虽然可行，但是由于事先无法预知哪些方格能够只有唯一灌溉的方向，因此须顺序判断每一个方格，因此时间复杂度会比较大。为了避免反复查找，那就必须对每个方格的每个灌溉方向进行实时的更新。同时我们需要将这些方格按可被灌溉的方向数有序化的在数组中，使得不必查找即可直接用 O(1)的时间找到可以直接判断的方格。由于需要实时更新，因此所采用的数据结构必须考虑到能够进行。为了能够实时更新每个方格的状态，相应的同时也必须实时更新每个喷水龙头在四个方向上的灌溉距离，使得在对灌溉距离

10、进行修改时，可以迅速地找到需要更新的方格（灌溉距离减少后会有一部分原先可以灌溉的方格不能被灌溉）。4具体的操作步骤对于一个任意一个方格(i,j)，需要知道其四个方向上可以被哪些喷水龙头灌溉。当然确定一个方格的灌溉方案，会影响到其他方格。例如，看一下后面这个例子。箭头表示喷水龙头能够灌溉的距离若黑色方格被 4 号喷水龙头灌溉（金色），则其他喷水龙头的可灌溉距离将受到影响：2(3)1(5)3(5)4(4)2(3)1(5)3(5)4(4)同样还要修改每个方格的可能灌溉方向，显然打横线的方格将不能被 3 号喷水龙头（绿色）灌溉，打竖线的方格将不能被 1 号喷水龙头灌溉（蓝色）。然后要同样将打斜方格的方

11、格像黑色方格一样处理。并且需要修改 4 号喷水龙头的水量，同时也需要调整其灌溉范围。在具体实现时，还需要每个喷水龙头在各个方向上的实际灌溉距离，这最终也同时是的输出结果。5编程实现的细节考虑到上面的分析，需要状态的数据量是很大的，互相的关系也十分密切。由于仍然要借助搜索，因此回溯时要考虑如何返回上一个状态。能够直接确定的方格都事先确定，因此每进行一步搜索对于状态的改变都可能非常巨大，使其恢复到上一个状态的操作不仅繁琐，而且在时间复杂度方面也不一定有优势。因此定义一种数据类型纪录整个状态，并以这样一个数据类型的变量作为参数进行搜索，就免去了恢复的操作。如下定义数据类型：type rtype=ar

12、ray1.maxk,1.4 of stype=recordsum:eger;eger;id:array1.maxk,0.5 ofeger;map:array1.maxn,1.maxm,0.6 ofeger;hl:array1.4 ofeger;mh:array0.maxn*maxm,1.2 of result:rtypeend;eger;var sd:stype;这样一个数据类型可以sd.sum 表示整个n*m 的网格上先前提到的一些状态量。下未覆盖的方格数。sd.id 数组用于描述每个喷水龙头的状态。sd.idi,0表示第 i 个喷水龙头余的水量，sd.idi,1、sd.idi,2、sd.i

13、di,3、sd.idi,4分别表示第 i 喷水龙头在四个方向上可达的距离（需考虑喷水龙头的水量及是否会遇到阻挡）。sd.idi,5表示可以四个方向中仍能延伸的方向个数。sd.map 数组中描述每个方格的状态。sd.mapi,j,0表示第(i,j)方格被第 sd.mapi,j,0个喷水龙头灌溉，若还未被灌溉则 sd.mapi,j,0=0 。sd.mapi,j,1、sd.mapi,j,2、sd.mapi,j,3、sd.mapi,j,4分别表示四个方向上能够灌溉到方格(i,j)的喷水龙头，0 表示方格(i,j)在此方向上不可能被灌溉。sd.mapi,j,5表示四个方向能被灌溉的方向数。sd.mapi

14、,j,6表示(i,j)在stype.mh 数组中位置，关于这个数组即先前提到有序可的队列。sd.mh 是方格的有序队列，以 sd.mapi,j,5的大小排序，这是为了从方格中找到能够直接判断的方格。由于 sd.mapi,j,5=1 即(i,j)只能由一个方向上的喷水龙头灌溉，则此方格可以直接确定，使用这个有序队列可以用 O(1)的时间找到符合要求的方格。sd.hl 用于sd.mh 数组，sd.hlk表示所有满足 mapi,j,5=k 的方格(i,j)在队列中最先的位置序号。由于在直接确定时会影响到周围的喷水龙头及方格，因此每个方格的可达方向数都始终在变化。但我并没有采用常用的堆来这个数组，因为

15、 mapi,j5在0,1,2,3,4中取值，因此可以采用如下进行。procedure swap(i,j:eger); beginsd.mh0:=sd.mhi;sd.mhi:=sd.mhj;sd.mhj:=sd.mh0; sd.mapsd.mhi,1,sd.mhi,2,6:=i;sd.mapsd.mhj,1,sd.mhj,2,6:=j; end;procedure fix(x,y:eger); beginswap(sd.mapx,y,6,sd.hlsd.mapx,y,5); inc(sd.hlsd.mapx,y,5);dec(sd.mapx,y,5);if (sd.mapx,y,0=0) and

16、 (sd.mapx,y,5=0) then er:=true;end;上述过程将方格(x,y)在队列中的位置与和方格(x,y)方向数相同的在队列中的位置最前的方格交换位置，并将方向数为 sd.mapx,y,5的最先位置指针向后移了一位，并将方格(x,y)的方向数（sd.mapx,y,5）减少 1。并且在过程中进行了判错处理，即方格(x,y)还未被灌溉，但其可灌溉的方向已经为 0 的情况，er 为判错标志。sd.result 用于 每个喷水龙头在四个方向上已确定的灌溉距离。sd.resulti,1、 sd.resulti,2、sd.resulti,3、sd.resulti,4分别表示四个方向上的

17、灌溉距离。并且采用数据类型 rtype 是为了找到一个可行解时方便，可以直接赋值 ans:=sd.result。现在来看一下确定一个方格的灌溉方向，需要修改状态中的哪些量。这个操作如下过程完成：procedure deal(x,y,d:eger); var i,j,l,u,v,x1,y1:eger; beginfor i:=1 to 4 do/调整其他方向上喷水龙头的灌溉距离以及调整影响到的方格的灌溉方向if id then beginv:=sd.mapx,y,i;/喷水龙头if v0 then/若此方向上可能被灌溉 beginj:=abs(sv,1-x)+abs(sv,2-y);/计算喷水龙

18、头的位置距离/s 数组每个喷水龙头的位置及总水量，sv,1、sv,2分别表示第v 个喷水龙头的 x,y 坐标for u:=sd.idv,(i+1) mod 4+1 downto j do/修改由于被阻挡不可能再被灌溉的方格/由于 1 方向的反方向是 3，2 方向的反方向是 4，方向 i 的反方向就是(i+1) mod 4+1beginx1:=sv,1+u*w(i+1) mod 4+1,1;y1:=sv,2+u*w(i+1) mod 4+1,2;/计算方格位置，w 数组为四个方向的位置改变量sd.mapx1,y1,i:=0; /减少一个方向 fix(x1,y1);/调整队列if er then/

19、判错 exit;end;if j-1sd.resultv,(d+1) mod 4+1 then/更新喷水龙头的已达距离 sd.resultv,(d+1) mod 4+1:=j;dec(sd.idv,0);/减少喷水龙头的水量 dec(sd.sum);/减少剩余未被灌溉的方格数 for i:=1 to 4 doif sd.idv,isd.resultv,i+sd.idv,0 then/由于水量减少调整喷水龙头各个方向上的可达距离 beginfor l:=sd.idv,i downto sd.resultv,i+sd.idv,0+1 do begin/修改将不能被灌溉的方格的可灌溉方向x1:=sv

20、,1+l*wi,1;/计算方格位置 y1:=sv,2+l*wi,2;sd.mapx1,y1,(i+1) mod 4+1:=0;/减少一个方向 fix(x1,y1);/调整队列if er then/判错 exit;end;sd.idv,i:=sd.resultv,i+sd.idv,0;/调整喷水龙头的可达距离 if sd.idv,i=sd.resultv,i then/若可达距离与已达距离相同，方向数减少 1 dec(sd.idv,5);end;if (j1) and (sd.mapx+wd,1,y+wd,2,0=0) then/同样处理灌溉的一直线上下一个方格 deal(x+wd,1,y+wd

21、,2,d);end;已经可以实现确定一个方格灌溉方向，并对相关的状态进行调整。然后目标就是确定哪些方格的灌溉方向。注意到 在状态调整的过程中一直在调整 sd.idi,5，如果某个喷水龙头的可灌溉方向只剩下一个，则 也可以直接确定其灌溉的方格。可以用如下的过程完成这些操作：procedure check; var i,j,x,y:eger;again:begin;again:=true;/是否可能还有可以直接确定的方格 while again dobeginwhile again do beginagain:=false;/置查找结束标志if sd.hl1t then/所有的方格已灌溉/变量 t

22、的是初始时所有未灌溉的方格数break;x:=sd.mhsd.hl1,1;/找到一个可灌溉方向数为 1 的方格y:=sd.mhsd.hl1,2;if sd.mapx,y,51 then/如果找不到可以直接确定的方格 break;for i:=1 to 4 doif sd.mapx,y,i0 then/找到唯一的方向 beginagain:=true;/置标志为继续查找 deal(x,y,i);/处理此方格if er then/判错 exit;end;end;for i:=1 to k do beginif (sd.idi,00) and (sd.idi,5=0) then/若某喷水龙头还有剩余

23、水量，但已无可灌溉的方向则判错 beginer:=true; exit;end;if sd.idi,5=1 then/只有唯一的可灌溉方向 for j:=1 to 4 doif sd.idi,jsd.resulti,j then/找到唯一的方向 beginagain:=true;/置标志 x:=si,1+sd.idi,j*wj,1;y:=si,2+sd.idi,j*wj,2;/计算可灌溉的最远的方格 deal(x,y,(j+1) mod 4+1);/处理此方格if er then/判错 exit;end;end;end;end;然后就是搜索及回溯的过程：procedure search(sd:

24、stype;p,q,r:eger); var i,j,v:eger;er:begin;er:=false;/置标志为未发现错误if r0 then/确定一个方格（不能直接判断时进行一步搜索，由调用时给出） deal(p,q,r);check;/确定所有能够直接判断的方格 if er then/判错则回溯exit;if sd.sum=0 then/已找到可行方案 beginans:=sd.result;/方案finish:=true;/置结束标志 exit;/回溯end;/不能直接确定剩下的方格，因此进行搜索 for i:=1 to n dofor j:=1 to m doif sd.mapi,

25、j,0=0 then/找到任意一个未灌溉的方格 beginfor v:=1 to 4 do/考虑每个方向 if sd.mapi,j,v0 thenbeginsearch(sd,i,j,v);/进行一步搜索 if finish then/如结束则回溯exit;end;exit;/每个方格都必须被灌溉，因此如果此方格不能被灌溉，则回溯 end;end;然后只剩下主过程，即进行输入输出及初始化的过程，这一步没什么难度：const inp=irrigation.in;/输入输出文件名 out=irrigation.out;maxn=30;/数据范围 maxm=30; maxk=200;w:array1

26、.4,1.2 of -1.1=(0,1),(1,0),(0,-1),(-1,0);/定义四个方向上位置改变量type rtype=array1.maxk,1.4 of stype=recordsum:eger;eger;/类型定义id:array1.maxk,0.5 ofeger;map:array1.maxn,1.maxm,0.6 ofeger;hl:array1.4 ofeger;mh:array0.maxn*maxm,1.2 of result:rtype;end;var sd:stype;/状态eger;s:array1.maxk,1.3 ofeger;/描述喷水龙头 t,i,j,l,

27、x,y,v,m,n,k:eger;ans:rtype;/结果finish:begin;/结束标志assign(input,inp); reset(input); fillchar(sd,sizeof(sd),0); read(n,m,k);/输入部分 for i:=1 to k dobeginread(si,1,si,2,si,3);sd.mapsi,1,si,2,0:=i;/调整状态 inc(sd.sum,si,3);/计算剩余未被灌溉的方格数 sd.idi,0:=si,3;/喷水龙头的剩余水量赋初值end;for i:=1 to k do for j:=1 to 4 dobeginx:=s

28、i,1;y:=si,2;for v:=1 to si,3 dobegin/计算每个喷水龙头的初始灌溉距离 x:=x+wj,1;y:=y+wj,2;if (x1) or (yn) or (ym) then break;/越界跳出if sd.mapx,y,00 thenbreak; /遇到（喷水龙头）sd.mapx,y,(j+1) mod 4+1:=i;/对方格(x,y)增加一个可被灌溉方向 inc(sd.mapx,y,5);/增加一个方向数inc(sd.idi,j);/增加喷水龙头的灌溉距离 end;if sd.idi,j0 then/如果方向上灌溉距离大于 0 则说明增加了一个灌溉方向inc(

29、sd.idi,5);end;l:=0;for v:=1 to 4 do for i:=1 to n dofor j:=1 to m doif sd.mapi,j,5=v then begininc(l);/计算位置序号sd.mapi,j,6:=l;/序号sd.mhl,1:=i;/进入队列 sd.mhl,2:=j;if sd.hlv=0 then sd.hlv:=l;/设指针位置end;t:=l;/总的未灌溉方格数 for i:=3 downto 1 doif sd.hli=0 thensd.hli:=sd.hli+1;/调整指针位置 finish:=false; /置未找到解 search(s

30、d,0,0,0); /开始搜索 assign(output,out);rewrite(output);for i:=1 to k do/输出解 beginfor j:=1 to 3 do write(ansi,j, );wrin(ansi,4); end;close(output);end.6总结至此整个过程便实现了，应该说解决的过程步骤还是比较清晰的，让来回顾一下整个算法。找到了解题的一个关键，即很多的方格被灌溉的方案是唯一的，在此基础上再进行搜索。具体实现时，采用了对整个网格的状态（包括喷水龙头及每个方格的状态）进行实时的更新，并采用队列进行有序化的。然后要来分析一下算法的效率。具体定量的

31、计算很难办到，只能定性的来分析一下效果。的算法目标是尽量减少搜索量，因此每一步都事先将可确定的方格都确定了，应该可以想见这样的搜索量应该是比较小的。如果说可确定的方格很少，那相应的解应该很多，因此不难搜索得到一个可行解。不过这样的算法也有其缺点，忌讳扩展的状态过多，由于每个状态数据量非常大，达到 20k。因此扩展过多的节点会造成两个问题，一是时间上反而成了主要瓶颈，二是使用堆栈空间也比较大。总体来说算法遇到特别慢的数据的有两个特点，一是要灌溉方案可能性较多（不会造成直接判定掉太多的方格），还要灌溉方案的局部需要有一些牵制，才不会造成随便进行几步搜索就能找到一个可行解。7数据分析发现由于题目要求

32、保证有一种完的方案，这样的题目类型对数据的要求也很严格。由于保证有解，那么在出大规模数据时，是不能够事先确定好喷水龙头的位置的，这是由于并不知道这样一个喷水龙头的布局能否找到一种可行方案。也就是说在出大规模在 n*m数据时，是通过一个可行方案的布局反推出喷水龙头的位置及确定的水量（即的网格上划，直至覆盖完所有的方格）。既然如此，应该说出数据并非一件易事，在构造一个可行方案的布局时是也无法预知最后喷水龙头的数目。发现出大规模数据时是无法预知到底有多少可行方案，更无法预知搜索的效率。因为也很难直观的了解喷水龙头的位置及水量到底能够对应哪些可行方案。那么这样的情况就会造成无法刻意的去寻找一些特别慢的

33、数据（这些数据也没有的表面特征），这样的数据无法通过手工构造。因此为了测试算法的效果，我采用了大量的随机数据。并且手工给出了一个棋盘布局（类似黑白染色）的数据，应该说这是一个可行解很多，状态很多的典型。那么下面给出了一张表格，粗略的显示了算法的效果。下面表格中前 49 个数据规模为 n=30，m=30，第 50 个数据为 n=20，m=20喷头数用时喷头数用时喷头数用时011901s181971s351941s021851s191751s361871s031991s201951s372001s041971s211931s382001s051921s221811s391951s061861s231925min071901s241871s411971s081831s251991s421971s091971s261901s431881s101941s271931s441801s1