图论与搜索在noip中的应用课件

《图论与搜索在noip中的应用课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、NOIP范围内的搜索与图论------大连24中杨文冕（一）枚举及其应用1.爆搜2.弗洛伊德算法3.网络流（这个暂时不考虑）IOI'94-Day2考虑将如此安排在一个3x3行列中的九个时钟:目标要找一个最小的移动顺序次将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。移动方法受影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHIInput第1-3行:三个空格分开的数字，

2、每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。Output单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。如果有多种方案，输出那种使的连接起来数字最小的方案。(举例来说5246<9311)。SampleInput9912666636SampleOutput4589思路枚举每个操作操作了多少次,最多是3次的,因为每次加3,4次就回到原来的样子了!!（你咋想的？宽搜？深搜？时间空间卡死你……想多了吧……枚举才是王道！）佛洛依德太简单，就不用例题了吧……（二）深搜及其应用（

3、1）.回溯（深度爆搜）（有兴趣的可以研究一下dancinglinks)（2）.图的深度优先遍历（以及拓扑排序）（3）.强连接分量爆搜（noip2009,靶型数独）描述Description小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在9格宽×9格高的大九宫格中有9个3格宽×3格高的小九宫格（用粗黑色线隔开的）。在这个大

4、九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）上图具体的分值分布是：最里面一格（黄色区域）为10分，黄色区域外面的一圈（红色区域）每个格子为9分，再外面一圈（蓝色区域）每个格子为8分，蓝色区域外面一圈（棕色区域）每个格子为7分，最外面一圈（白色区域）每个格子为6分，如上图所示。比赛的要求是

5、：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。【输入样例1】7009000011000059000002000800050200030000006484130000000070020902010608040805

6、04012【输入样例2】000702453900008000740005010195080000070000025030579108000601000060900001000000006【输出样例1】2829【输出样例2】2852图的深度优先遍历及拓扑排序proceduresou(x:longint);vari:longint;beginrec[x]:=true;fori:=1tolink[x,0]doifnotrec[link[x,i]]thensou(link[x,i]);inc(p);a[p]:=x;end;其中rec是是否遍历过

7、的标记，link是邻接表。当然，在主程序中需要有这一句：fori:=1tondoifrec[i]=falsethensou(i);而不是直接的dfs(1)，因为节点1并不一定能到达所有节点。这是初学者常犯的一个错误。当然，DFS进行的顺序并不一定是按节点编号顺序。一般按节点编号顺序DFS只是为了方便，有时我们必须以不同的顺序进行DFS（比如下面将要谈到的Kosaraju算法）。例题描述一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使B在A学校的分发列表中，A也不一定在B学

8、校的列表中。你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有