搜搜考试网NOIP2012普及组复赛第4题文化之旅
来源：学生作业帮 编辑：搜搜考试网作业帮 分类：数学作业 时间：2024/06/25 07:05:31
NOIP2012普及组复赛第4题文化之旅
求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.
不要抄袭，请求别的更高效的做法或剪枝方法。
求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.
不要抄袭，请求别的更高效的做法或剪枝方法。
满分搜索的话,按理用下面几个剪枝就可以了.
1、最优性剪枝 （Ans < Nowdist + MinDist）
（Nowdist当前走过的路程,MinDist至少还要走多远）.
2、删去所有影响终点的城市（不可能走到的……）
3、倒搜
说实话给 PJ 组的写 STD 时是这么写的……AC过了.
虽然怎么说倒搜似乎有些说不过.
另把倒搜换成下面的剪枝也是可以过的.
设定一个X,从终点向外拓展X层.
每走一个城市看是否这X层中的任意一层被封锁.
上述的确有些郁闷,因为X取小作用不大,取大又降低了程序运行速度.
可以考虑将所有拓展层全部求出来.每2、3层跳跃一次.
100个点的图如果想卡人的话,层数不会太多的,最多10层左右.
不过后面的没有实现了.STD X 取1就可以过.
程序在学校的说……明天中午发过来>_
再问： 现在能发过来了么？
再答： 嗯……私信发了.
再问： 有没有Free Pascal 的程序？C我当真看不懂...
再答： = =、 给你伪代码自己打着吧...... procedure DFS (nowcity, nowdist, culture) begin if nowcity = t then //是否到达目标城市 do if nowdist < ans then ans := nowdist; //比当前答案小就更新 exit //退出 end if nowdist > ans then exit //剪枝1，比当前答案大就退出. for each E(nowcity, nextcity) //枚举每条当前城市的出边 if nextcity ∉ cultrue then //如果到达的城市没有被登记过 do Add nextcity to culture //登记到达的城市，并且将到达的城市所影响 Add cities influenced to culture 的城市也登记上） DFS(nextcity, nowdist + dist(nowcity, nextcity), culture) //继续搜索 Clear culture //回溯操作. end end; 主程序都是预处理一些东西而已……DFS过程就上面那样子. 实在不行百度应该有……
1、最优性剪枝 （Ans < Nowdist + MinDist）
（Nowdist当前走过的路程,MinDist至少还要走多远）.
2、删去所有影响终点的城市（不可能走到的……）
3、倒搜
说实话给 PJ 组的写 STD 时是这么写的……AC过了.
虽然怎么说倒搜似乎有些说不过.
另把倒搜换成下面的剪枝也是可以过的.
设定一个X,从终点向外拓展X层.
每走一个城市看是否这X层中的任意一层被封锁.
上述的确有些郁闷,因为X取小作用不大,取大又降低了程序运行速度.
可以考虑将所有拓展层全部求出来.每2、3层跳跃一次.
100个点的图如果想卡人的话,层数不会太多的,最多10层左右.
不过后面的没有实现了.STD X 取1就可以过.
程序在学校的说……明天中午发过来>_
再问： 现在能发过来了么？
再答： 嗯……私信发了.
再问： 有没有Free Pascal 的程序？C我当真看不懂...
再答： = =、 给你伪代码自己打着吧...... procedure DFS (nowcity, nowdist, culture) begin if nowcity = t then //是否到达目标城市 do if nowdist < ans then ans := nowdist; //比当前答案小就更新 exit //退出 end if nowdist > ans then exit //剪枝1，比当前答案大就退出. for each E(nowcity, nextcity) //枚举每条当前城市的出边 if nextcity ∉ cultrue then //如果到达的城市没有被登记过 do Add nextcity to culture //登记到达的城市，并且将到达的城市所影响 Add cities influenced to culture 的城市也登记上） DFS(nextcity, nowdist + dist(nowcity, nextcity), culture) //继续搜索 Clear culture //回溯操作. end end; 主程序都是预处理一些东西而已……DFS过程就上面那样子. 实在不行百度应该有……