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

NOIP范围内的搜索与图论 大连24中杨文冕 一 枚举及其应用 1 爆搜2 弗洛伊德算法3 网络流 这个暂时不考虑 IOI 94 Day2 考虑将如此安排在一个3x3行列中的九个时钟 目标要找一个最小的移动顺序次将所有的指针指向12点 下面原表格列出了9种不同的旋转指针的方法 每一种方法都叫一次移动 选择1到9号移动方法 将会使在表格中对应的时钟的指针顺时针旋转90度 移动方法受影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHI Input第1 3行 三个空格分开的数字 每个数字表示一个时钟的初始时间 3 6 9 12 数字的含意和上面第一个例子一样 Output单独的一行包括一个用空格分开的将所有指针指向12 00的最短移动顺序的列表 如果有多种方案 输出那种使的连接起来数字最小的方案 举例来说5246 9311 SampleInput9912666636SampleOutput4589 思路 枚举每个操作操作了多少次 最多是3次的 因为每次加3 4次就回到原来的样子了 你咋想的 宽搜 深搜 时间空间卡死你 想多了吧 枚举才是王道 佛洛依德太简单 就不用例题了吧 二 深搜及其应用 1 回溯 深度爆搜 有兴趣的可以研究一下dancinglinks 2 图的深度优先遍历 以及拓扑排序 3 强连接分量 爆搜 noip2009 靶型数独 描述Description小城和小华都是热爱数学的好学生 最近 他们不约而同地迷上了数独游戏 好胜的他们想用数独来一比高低 但普通的数独对他们来说都过于简单了 于是他们向Z博士请教 Z博士拿出了他最近发明的 靶形数独 作为这两个孩子比试的题目 靶形数独的方格同普通数独一样 在9格宽 9格高的大九宫格中有9个3格宽 3格高的小九宫格 用粗黑色线隔开的 在这个大九宫格中 有一些数字是已知的 根据这些数字 利用逻辑推理 在其他的空格上填入1到9的数字 每个数字在每个小九宫格内不能重复出现 每个数字在每行 每列也不能重复出现 但靶形数独有一点和普通数独不同 即每一个方格都有一个分值 而且如同一个靶子一样 离中心越近则分值越高 如图 上图具体的分值分布是 最里面一格 黄色区域 为10分 黄色区域外面的一圈 红色区域 每个格子为9分 再外面一圈 蓝色区域 每个格子为8分 蓝色区域外面一圈 棕色区域 每个格子为7分 最外面一圈 白色区域 每个格子为6分 如上图所示 比赛的要求是 每个人必须完成一个给定的数独 每个给定数独可能有不同的填法 而且要争取更高的总分数 而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和 如图 在以下的这个已经填完数字的靶形数独游戏中 总分数为2829 游戏规定 将以总分数的高低决出胜负 由于求胜心切 小城找到了善于编程的你 让你帮他求出 对于给定的靶形数独 能够得到的最高分数 输入样例1 700900001100005900000200080005020003000000648413000000007002090201060804080504012 输入样例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是是否遍历过的标记 link是邻接表 当然 在主程序中需要有这一句 fori 1tondoifrec i falsethensou i 而不是直接的dfs 1 因为节点1并不一定能到达所有节点 这是初学者常犯的一个错误 当然 DFS进行的顺序并不一定是按节点编号顺序 一般按节点编号顺序DFS只是为了方便 有时我们必须以不同的顺序进行DFS 比如下面将要谈到的Kosaraju算法 例题 描述一些学校连入一个电脑网络 那些学校已订立了协议 每个学校都会给其它的一些学校分发软件 称作 接受学校 注意即使B在A学校的分发列表中 A也不一定在B学校的列表中 你要写一个程序计算 根据协议 为了让网络中所有的学校都用上新软件 必须接受新软件副本的最少学校数目 子任务A 更进一步 我们想要确定通过给任意一个学校发送新软件 这个软件就会分发到网络中的所有学校 为了完成这个任务 我们可能必须扩展接收学校列表 使其加入新成员 计算最少需要增加几个扩展 使得不论我们给哪个学校发送新软件 它都会到达其余所有的学校 子任务B 一个扩展就是在一个学校的接收学校列表中引入一个新成员 格式PROGRAMNAME schlnetINPUTFORMAT输入文件的第一行包括一个整数N 网络中的学校数目 2 N 100 学校用前N个正整数标识 接下来N行中每行都表示一个接收学校列表 分发列表 第i 1行包括学校i的接收学校的标识符 每个列表用0结束 空列表只用一个0表示 OUTPUTFORMAT你的程序应该在输出文件中输出两行 第一行应该包括一个正整数 子任务A的解 第二行应该包括子任务B的解 SAMPLEINPUT fileschlnet in 524304500010SAMPLEOUTPUT fileschlnet out 12 Kosaraju算法 Kosaraju算法基于以下思想 强连通分量一定是某种DFS形成的DFS树森林 Kosaraju算法给出了更具体的方式 任意进行一次DFS 记录下每个节点的结束时间戳f i 按a i 的大小对节点进行排序 从小到大 以 的排序结果为顺序再进行一次DFS 所得的DFS树森林即为强连通分量 这次DFS可以用Floodfill进行 把每个强连通分量标上不同序号 这就是OI界传说中的 求强连两遍DFS的算法 比如上图 我们可以得到 d 1 1a 1 14d 2 2a 2 5d 3 6a 3 13d 4 3a 4 4d 5 7a 5 8d 6 9a 6 12d 7 10a 7 11根据f i 排序得 发现了什么 就是后序遍历 再按照这个顺序进行DFS即可 第二次深搜 染色 proceduresou2 x longint vari longint Begincol x color fori 1tolink2 x 0 doifcol link2 x i 0thensou2 link2 x i end 主程序 BEGINreadln n fori 1tondobeginread x whilex0dobegininc link i 0 link i link i 0 x inc link2 x 0 link2 x link2 x 0 i 2 将原图每条边进行反向 read x end end fillchar rec sizeof rec 0 fori 1tondo 1 对原图进行DFS ifnotrec i thensou i color 0 fori pdownto1do 并将出栈顺序a i 进行逆序 得到的顺序就是拓扑顺序 ifcol a i 0thenbegininc color sou2 a i 3 按照1中生成顺序再进行DFS染色染成同色的是一个强连通块 end END 统计出入度 fori 1tondo 统计各子图的入度和出度 forj 1tolink i 0 doifcol i col link i j thenifnotmap col i col link i j thenbeginmap col i col link i j true inc dout col i inc din col link i j end fori 1tocolordobeginifdin i 0theninc ans 入度为零的子图个数即第一问答案 ifdout i 0theninc tt dout ifdin i 0theninc tt din end writeln ans writeln max tt din tt dout 出入度和较大的即第二问答案 Noip2009原题 最优贸易 C国有n个大城市和m条道路 每条道路连接这n个城市中的某两个城市 任意两个城市之间最多只有一条道路直接相连 这m条道路中有一部分为单向通行的道路 一部分为双向通行的道路 双向通行的道路在统计条数时也计为1条 C国幅员辽阔 各地的资源分布情况各不相同 这就导致了同一种商品在不同城市的价格不一定相同 但是 同一种商品在同一个城市的买入价和卖出价始终是相同的 商人阿龙来到C国旅游 当他得知同一种商品在不同城市的价格可能会不同这一信息之后 便决定在旅游的同时 利用商品在不同城市中的差价赚回一点旅费 设C国n个城市的标号从1 n 阿龙决定从1号城市出发 并最终在n号城市结束自己的旅行 在旅游的过程中 任何城市可以重复经过多次 但不要求经过所有n个城市 阿龙通过这样的贸易方式赚取旅费 他会选择一个经过的城市买入他最喜欢的商品 水晶球 并在之后经过的另一个城市卖出这个水晶球 用赚取的差价当做旅费 由于阿龙主要是来C国旅游 他决定这个贸易只进行最多一次 当然 在赚不到差价的情况下他就无需进行贸易 假设C国有5个大城市 城市的编号和道路连接情况如下图 单向箭头表示这条道路为单向通行 双向箭头表示这条道路为双向通行 假设1 n号城市的水晶球价格分别为4 3 5 6 1 阿龙可以选择如下一条线路 1 2 3 5 并在2号城市以3的价格买入水晶球 在3号城市以5的价格卖出水晶球 赚取的旅费数为2 阿龙也可以选择如下一条线路1 4 5 4 5 并在第1次到达5号城市时以1的价格买入水晶球 在第2次到达4号城市时以6的价格卖出水晶球 赚取的旅费数为5 现在给出n个城市的水晶球价格 m条道路的信息 每条道路所连接的两个城市的编号以及该条道路的通行情况 请你告诉阿龙 他最多能赚取多少旅费 输入格式第一行包含2个正整数n和m 中间用一个空格隔开 分别表示城市的数目和道路的数目 第二行n个正整数 每两个整数之间用一个空格隔开 按标号顺序分别表示这n个城市的商品价格 接下来m行 每行有3个正整数 x y z 每两个整数之间用一个空格隔开 如果z 1 表示这条道路是城市x到城市y之间的单向道路 如果z 2 表示这条道路为城市x和城市y之间的双向道路 数据范围 输入数据保证1号城市可以到达n号城市 对于10 的数据 1 n 6 对于30 的数据 1 n 100 对于50 的数据 不存在一条旅游路线 可以从一个城市出发 再回到这个城市 对于100 的数据 1 n 100000 1 m 500000 1 x y n 1 z 2 1 各城市水晶球价格 100 输出格式共1行 包含1个整数 表示最多能赚取的旅费 如果没有进行贸易 则输出0 样例输入5543561121141232351452样例输出5 解题思路 首先考虑没有环的情况 此时1 n之间要么无法连通 要么只存在一些单向的无环路径 对于每一条路径 由于不能 回头 走到某个点i的极优获利显然是 i的费用 路径上此点之前的点的最小费用 而此路径的最大获利便是取获利最大的点 但是还有很多数据是有环的 也就是对于有些点对 a b 在a走到b之后 b仍然可以走回到a 在图论中 我们把点集V 其中任意两个点可以互达 叫做强连通分量 由于强连通分量中的点可以互相到达 所以在一个强连通中的最大获利就是强连通中最贵的 最便宜的 我们把所有强连通分量求出来缩为两个点之后 1与n之间只存在一些无环路径 对于这些单向的无环路径我们只需要扫描一遍便可求出最大获利 强连通缩为两个点的具体做法 把一个强连通缩为a b两个点 连 a b 边 a的费用为强连通中最便宜的 b的费用为强连通中最贵的 把指强连通图向强连通中任何一个点的所有边改为指向a 把强连通中任何一点指向强连通外部的边改为由b指出 这样构出来的保证与原图等价 补充一种图的存储结构 前向星 应用范围 稀疏图 用数组模拟邻接表会爆内存的图 存储与遍历 遍历 Proceduredfs x longint beginFori 1tolen x dobegintop head x now top i 1 Point c now Dfs now end 存储 BeginReadln m Fori 1tomdobeginReadln x y r i x c i y end Qsort r i 1 m Fori 1tomdobeginTemp r i Iftempr i 1 thenhead temp I inc len temp end End 一种特殊的前向星 链式前向星 相见资料 三 广搜及其应用 广度爆搜图的广度优先遍历 FLOODFILL 单元最短路 spfa Dijkstra 最小生成树 prim 广搜染色 二分图的检验 广度爆搜 细胞 cell 问题描述 一个矩形阵列由数字0 9组成 数字1 9代表细胞 细胞的定义是沿细胞数字上下左右如果还是细胞数字则为同一细胞 求给定矩阵阵列的细胞个数 输入格式 第一行为整数m n 接着m行 每行n个数字 输出格式 细胞的个数 输入样例 cell in4100234500067103456050020456006710000000089 输出样例 cell out4 传说中的Floodfill procedureflood fill x y longint beginif x 0 or y 0 or x n or y m ornotv x y thenexit 超出了边界或者已经到过v x y false 标记为已经到过flood fill x 1 y 下flood fill x 1 y 上flood fill x y 1 右flood fill x y 1 左end Spfa 我们用数组d记录每个结点的最短路径估计值 而且用邻接表来存储图G 我们采取的方法是松弛 设立一个先进先出的队列用来保存待优化的结点 优化时每次取出队首结点u 并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作 如果v点的最短路径估计值有所调整 且v点不在当前的队列中 就将v点放入队尾 这样不断从队列中取出结点来进行松弛操作 直至队列空为止 procedurespfa beginfillchar q sizeof q 0 h 0 t 0 队列fillchar v sizeof v false v i 判断i是否在队列中fori 1tondodist i maxint 初始化最小值inc t q t 1 v 1 true dist 1 0 这里把1作为源点whilehtdobeginh hmodn 1 x q h v x false fori 1tondoif cost x i 0 and dist x cost x i dist i thenbegindist i dist x cost x i ifnot v i thenbegint tmodn 1 q t i v i true end end end end Spfa代码 Noip2009原题 最优贸易 C国有n个大城市和m条道路 每条道路连接这n个城市中的某两个城市 任意两个城市之间最多只有一条道路直接相连 这m条道路中有一部分为单向通行的道路 一部分为双向通行的道路 双向通行的道路在统计条数时也计为1条 C国幅员辽阔 各地的资源分布情况各不相同 这就导致了同一种商品在不同城市的价格不一定相同 但是 同一种商品在同一个城市的买入价和卖出价始终是相同的 商人阿龙来到C国旅游 当他得知同一种商品在不同城市的价格可能会不同这一信息之后 便决定在旅游的同时 利用商品在不同城市中的差价赚回一点旅费 设C国n个城市的标号从1 n 阿龙决定从1号城市出发 并最终在n号城市结束自己的旅行 在旅游的过程中 任何城市可以重复经过多次 但不要求经过所有n个城市 阿龙通过这样的贸易方式赚取旅费 他会选择一个经过的城市买入他最喜欢的商品 水晶球 并在之后经过的另一个城市卖出这个水晶球 用赚取的差价当做旅费 由于阿龙主要是来C国旅游 他决定这个贸易只进行最多一次 当然 在赚不到差价的情况下他就无需进行贸易 假设C国有5个大城市 城市的编号和道路连接情况如下图 单向箭头表示这条道路为单向通行 双向箭头表示这条道路为双向通行 假设1 n号城市的水晶球价格分别为4 3 5 6 1 阿龙可以选择如下一条线路 1 2 3 5 并在2号城市以3的价格买入水晶球 在3号城市以5的价格卖出水晶球 赚取的旅费数为2 阿龙也可以选择如下一条线路1 4 5 4 5 并在第1次到达5号城市时以1的价格买入水晶球 在第2次到达4号城市时以6的价格卖出水晶球 赚取的旅费数为5 现在给出n个城市的水晶球价格 m条道路的信息 每条道路所连接的两个城市的编号以及该条道路的通行情况 请你告诉阿龙 他最多能赚取多少旅费 输入格式第一行包含2个正整数n和m 中间用一个空格隔开 分别表示城市的数目和道路的数目 第二行n个正整数 每两个整数之间用一个空格隔开 按标号顺序分别表示这n个城市的商品价格 接下来m行 每行有3个正整数 x y z 每两个整数之间用一个空格隔开 如果z 1 表示这条道路是城市x到城市y之间的单向道路 如果z 2 表示这条道路为城市x和城市y之间的双向道路 数据范围 输入数据保证1号城市可以到达n号城市 对于10 的数据 1 n 6 对于30 的数据 1 n 100 对于50 的数据 不存在一条旅游路线 可以从一个城市出发 再回到这个城市 对于100 的数据 1 n 100000 1 m 500000 1 x y n 1 z 2 1 各城市水晶球价格 100 输出格式共1行 包含1个整数 表示最多能赚取的旅费 如果没有进行贸易 则输出0 样例输入5543561121141232351452样例输出5 Spfa的解法 用另类spfa 即求出最大最小值 求出从第一个点出发到其他点能买到水晶球的最小代价 将所有边反向以后 从N个点出发求出第N个点到第i个点能卖出水晶球的最大代价 这个代价对应于原图中第i个点到第N个点能获得的最大收益 对于每个点 用最大收益 最小代价更新答案即可 复杂度不好估计 不过稀疏图spfa的效率是很有保证的 Pirm与Dijkstra 都是广搜的变形 最小生成树Prim应用于稠密图 Procedureprim BeginFori 1tondoForj 1tondoIf ij and cost i j 0 Thencost i j maxlongint end Fori 1tondobeginMincost i cost 1 i Father i 1 end Fori 2tondobeginMin maxlongint Forj 1tondoIf mincost j 0 ThenbeginMin mincost j K j end Mincost k 0 Forj 1tondoIf mincost j cost k j beginmincost j cost k j father j k end end 另一种最小生成树克鲁斯卡尔应用于稀疏图 应用并查集 下次再讲 Dijkstra 单源最短路 Proceduredijkstra BeginV 1 true Forj 2tondobeginmin maxlongint Fori 1tondoIf notv i and a 1 i 0 and a 1 i 0 and a p i 0 thenIf a 1 i a 1 p a p i or a 1 i 0 thena 1 i a 1 p a p i End end Dijkstra如果进行堆优化可以将时间复杂度从o n 2 降为o n lg n 从而达到同spfa一样快 图的广度优先遍历与二分图的验证 广度优先遍历的基本思想1 从图中某个顶点V0出发 并访问此顶点 2 从V0出发 访问V0的各个未曾访问的邻接点W1 W2 Wk 然后 依次从W1 W2 Wk出发访问各自未被访问的邻接点 3 重复步骤2 直到全部顶点都被访问为止 二分图的概念 二分图又称作二部图 是图论中的一种特殊模型 设G V E 是一个无向图 如果顶点V可分割为两个互不相交的子集 A B 并且图中的每条边 i j 所关联的两个顶点i和j分别属于这两个不同的顶点集 iinA jinB 则称图G为一个二分图 二分图的验证 用染色法 把图中的点染成黑色和白色 首先任意取一个点染成白色 然后将其相邻的点染成黑色 再将其相邻的点染成白色 以此类推 直到所有点都被染色 染色后再次遍历 如果发现有相邻且同色的点 那么就退出 可知这个图并非二分图 二分图 非二分图 四 二分搜索 折半查找法也称为二分查找法 它充分利用了元素间的次序关系 采用分治策略 可在最坏的情况下用O logn 完成搜索任务 它的基本思想是 将n个元素分成个数大致相同的两半 取a n 2 与欲查找的x作比较 如果x a