解题报告程序玩具兵

1、CTSC2002 -Day1 -玩具兵问题描述的给他买了一盒玩具兵，其中有 K个步兵，KCTSC2002 -Day1 -玩具兵问题描述的给他买了一盒玩具兵，其中有 K个步兵，K 度 Hij，并且大得足以容纳所有的玩具兵。把所有的玩具兵都放到棋盘上去，Ti一个重要值R i 其相邻的格子中（但不能移动到棋盘外面去，最终使得每个挑选出的格子 i 恰好有 Ri 高度小于或等于B，步兵才可以从 A 移动到 B高度大于或等于B，骑兵才可以从 A 移动到 B (步兵，接下来的第三行包含T 个三元组(xi,yi,ri)，第i (步兵，接下来的第三行包含T 个三元组(xi,yi,ri)，第i 组代表第 i M

2、N i j Hij无错，选定的T 个格子的重要值之和保证等于 2K+1输出文件toy.out 仅包含一行，即使用超能力的最小次数T问题分析先排除讨厌的天兵，来看看如果只有K 个步兵和K 1 可以将任意一种目标方案，抽象成上述二分有向图 的一个完G(V1,V2,E 可以将任意一种目标方案，抽象成上述二分有向图 的一个完G(V1,V2,E a 个士兵连着第 b 个目标位置（，就表示第 a 个位置的士兵，最终到达目标位置 b力的总次数呢？就是E可以穷举超能力使用次数 w，从 0 次开始，每次对 Gww Gaa 标位置的同时，天兵还可以帮助 w a,bE察看G的完全匹配，而是最大匹配，求出匹配数a，察

3、看a+w 是否大于等于 2K+1程序由于w1，G 察看G的完全匹配，而是最大匹配，求出匹配数a，察看a+w 是否大于等于 2K+1程序由于w1，G Program Toy; = = = = = :Array1.4,1.2OfShort =Array1.MaxMN,1.MaxMN（高低士兵的=Array1.MaxK*2+1Of 位置:=Array1.MaxTOf目标位置x、y :Array1.MaxK*2,1.MaxTOf 网络图i,j示第ij个目标位置f 流量 0 或 :交叉路径的费用:=Array1.MaxTOf目标位置x、y :Array1.MaxK*2,1.MaxTOf 网络图i,j示第

4、ij个目标位置f 流量 0 或 :交叉路径的费用=Array1.(MaxK*2+1)*MaxT,1.3搜索队列eger; =Array1.MaxK*2+1,1.MaxT,1.2 最优费用i,j,ki、jk1步兵、2骑兵增广路径=Array0.MaxTOf=Array1.MaxT最优值更新标记=Array1.MaxT ;:地形（高低士兵的位置:目标位置:网络图i,j表示第i:到第j 个目标位置: 读入数据士兵的位置:目标位置:网络图i,j表示第i:到第j 个目标位置: 读入数据Procedure :For i:=1 to 2*k+1 Do For i:=1toTimiDo Fori:=1tonD

5、o Forj:=1tomDo Procedure Net数组（计算费用:对所有士兵进行宽度优先搜For i:=1to 2*k索s:=1;队首，队尾BFSs,3:=(i-1)div :对所有士兵进行宽度优先搜For i:=1to 2*k索s:=1;队首，队尾BFSs,3:=(i-1)div 对应位置费用Whiles=eForj:=1to4Do 向四个方向移动移动后的位置If (Nxn) (Nym)Then Continue;越界(MapNx,Ny=MapBFSs,1,BFSs,2) Or继续按照原Then 来的向低处或高处走Else 需要进行一If OptNx,Ny,Nz=$7F7F Then

6、没有更新过For l:=e-1 downto s顺序宽搜队列Else 需要进行一If OptNx,Ny,Nz=$7F7F Then 没有更新过For l:=e-1 downto s顺序宽搜队列OptBFSl,1,BFSl,2,BFSl,30Then根据父结点的值倒推出增光路径，存入该位置Then 父结点待扩展IfAimj.c0Then根据父结点的值倒推出增光路径，存入路径的长度Whilew0 找到增光路径则退出For i:=1toTFor j:=1to 2*k已扩展扩展目标位置所能反向到达的士兵If(Netj,i.f=1)弧第一次到达该位置Then 父结点待扩展已扩展兵If(Netj,i.f=

7、1)弧第一次到达该位置Then 父结点待扩展已扩展Until F; 对增广路径进行增广:Fori:=ndownto2Do 正向弧反向弧正向弧For i:=0to 2*ki w使用次数对所有士兵尝试增广For j:=1to 2*kIf(NotFinishj)And(Find(i,j,List)ThenBegin 满足IfBest+i=2*kThen For i:=0to 2*ki w使用次数对所有士兵尝试增广For j:=1to 2*kIf(NotFinishj)And(Find(i,j,List)ThenBegin 满足IfBest+i=2*kThen 测试环境： 编译器Free Pascal for Dos 机型el Celeron sor 735 +128MB 123456789WindowsXPal 2