当前位置:首页 >> 其它课程 >>

备战NOIP2012图论专项赛之一


备战 NOIP2012 图论专项赛之一
2012/6/8 第 1 题 位图
【时间限制】 1 Sec 【内存限制】 64 MB 【试题来源】 POI9909 【题目描述】 给出一个大小为 n 行*m 列的矩形位图。该位图的每一个象素点不是白色就是黑色,但 是至少有一个象素点是白色。在 i 行 j 列的象素点我们称为点(i,j) 。两个象素点 p1=(i1,j1

) 和 p2=(i2,j2)之间的距离定义如下: d(p1,p2)=|i1-i2|+|j1-j2| 现在的任务是:对于每一个象素点,计算它到最近的白色点的距离。如果它本身是白色 点,距离为 0。 【输入格式】 第 1 行:2 个整数 n,m(1<=n <=182,1<=m<=182) 接下来 n 行,每一行有一个长度为 m 的 0/1 字符串,描述一行象素点。如果点(i,j)为白 色,则值为 1,否则值为 0。 【输出格式】 共 n 行,每行有 m 个整数,数之间用 1 个空格分开,分别表示对应的象素点距离白色点的 距离。 【样例输入】 34 0001 0011 0110 【样例输出】 3210 2100 1001

第 2 题 外星人入侵
【时间限制】 1 Sec 【内存限制】 64 MB 【试题来源】 CTU OPEN 2011 【题目描述】 外星人入侵地球。可怕的吃人外星人正在全国各地依次序建立它们的基地。 全国共有 N(1≤ N ≤10,000)座城市, 城市编号 1~N。 城市之间有 M(0≤ M ≤100,000) 条双向道路相连。外星人计划建立 A(0≤A≤N)个基地。 你只有在距离当前所有外星人基地至少 K(1≤K≤100)单位长度的城市才能得到安全。 所以你必须赶快写一个程序决定走到哪里去。 【输入格式】 第 1 行:4 个整数 N, M, A, K 接下来 M 行,每行 3 个整数 T1, T2(1≤T1<T2≤N)和 D(1≤D≤100),表示城市 T1 与 T2 之间 有一条长度为 D 的道路。两个城市之间最多有一条直连道路。 接下来 A 行,每行 1 个整数 Bi(1≤Bi≤N),表示外星人依次序建的第 i 个基地所在的城市编 号。 【输出格式】 共 A 行,第 i 行 1 个整数,表示当外星人建好第 i 个基地后,距离当前所有基地 B1,B2,...,Bi 至少 K 长度的城市的数量。

【样例输入】 7633 121 131 251 361 141 472 2 1 4 【样例输出】 2 1 0

第 3 题 无线通讯网
【时间限制】 1 Sec 【内存限制】 64 MB 【试题来源】 waterloo local 2002.09.28 【题目描述】 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络: 每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。 任意两个配备了一条卫星电话线路的哨所均可以通话, 无论它们相距多远。 而只通过无 线电收发器通话的哨所之间的距离不能超过 D,这是受收发器的功率限制。收发器的功率越 高,通话距离 D 会更远,但同时价格也更贵。 收发器需要统一购买和安装,所以全部哨所只能选择安装一种型号的收发器。换句话说,每 一对哨所之间的通话距离都是同一个 D。 你的任务是确定收发器必须的最小通话距离 D, 使得每一对哨所之间至少有一条通话路 径(直接的或者间接的)。这段话很重要,附上原文: Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts. 【输入格式】 第 1 行:2 个整数 S(1 <= S <= 100)和 P(S < P <= 500),S 表示可安装的卫星电话的线路数,P 表示边防哨所的数量。 接下来 P 行,每行描述一个哨所的平面坐标(x,y),以 km 为单位,整数,0<=x,y<=10,000 【输出格式】 第 1 行:1 个实数 D,表示无线电收发器的最小传输距离。精确到小数点后 2 位。 【样例输入】 24 0 100 0 300 0 600 150 750 【样例输出】 212.13

第 4 题 砍树
【时间限制】 1 Sec 【内存限制】 64 MB 【试题来源】 USACO DEC 2004 【题目描述】 给出一个树形图("tree-shaped" network),有 N(1 <= N <= 10,000)个顶点。如果删除树上 某一个顶点,整棵树就会分割成若干个部分。显然,每个部分内部仍保持连通性。 现在问:删除哪个点,使得分割开的每个连通子图中点的数量不超过 N/2。如果有很多 这样的点,就按升序输出。 例如,如图所示的树形图,砍掉顶点 3 或者顶点 8,分割开的各部分满足条件。

【输入格式】 第 1 行:1 个整数 N,表示顶点数。顶点编号 1~N 第 2..N 行:每行 2 个整数 X 和 Y,表示顶点 X 与 Y 之间有一条边 【输出格式】 若干行,每行 1 个整数,表示一个符合条件的顶点的编号。如果没有顶点符合条件,则仅在 第 1 行上输出"NONE" 【样例输入】 10 12 23 34 45 67 78

89 9 10 38 【样例输出】 3 8

试题分析 第 1 题 位图
这道题最直白,所以比赛时,现场有 6 位同学 AC。 把二维网格平面上, 每个像素点作为一个顶点, 本题实质就是求所有黑色点到白色点的 最短距离。由于相邻格子之间的距离均为 1,因此这是一个等边权最短路问题,标准的方法 是用 BFS 求解。 如果直接求解,应该是枚举每一个黑色点,以它为源点进行 BFS,一旦搜索到一个白色 点,即找到它的最短距离。 分析这个算法的时间复杂度:整个图有 N*M 个顶点,每个顶点最多与四个方向的顶点 相邻,因此图的边数有 4*N*M。每一次 BFS 的时间为顶点数+边数,即 O(N*M)。而总共有 N*M 个顶点需要枚举,因此总的时间为 O(N^2*M^2)。对于 N≈200 的数据规模,是要超时 的。 反过来,如果把所有白色点的最短距离看成 0,与它们相邻的格子的最短距离就是 1, 而与相邻格子再相邻的格子的最短距离就为 2。因此,可以从所有白色格子为起点,向所有 黑色格子进行宽搜。一旦遇到某个黑色格子,它的最短距离就求出来了。 在实现时,先把所有白色格子入队,然后对队首元素,按四个方向扩展,计算它们的最 短距离。 这个算法的时间复杂度如何呢?由于每一个格点只需要入队一次, 出队一次, 所以整个 算法的复杂度为 O(N*M)。这就与枚举每个格子的时间相等,已经到达低限了。 当然,用 Dijkstra 和 SPFA 等带权最短路算法也可以。构图时,虚拟一个超级源点 S,连 向所有的白色格子,距离为 0。然后从 S 出发计算最短路。 这个算法的复杂度要比 BFS 高, 用基本的 Dijkstra 算法的最坏复杂度仍是 O(顶点^2), 即 是 O(N^2*M^2)。但由于图中边很稀疏,用 SPFA 就很好。 其实这里的 SPFA 与 BFS 已经没有区别了。 参考程序 1:BFS 参考程序 2:Dijkstra+Priority Queue

第 2 题 外星人入侵
很遗憾,这道稍微有点变化的最短路问题,把好多同学都拦住了。现场只有 1 人 AC。 这个题是比较明显的带权最短路问题, 但在基本的单源点最短路基础上有所变化。 本题 体现出动态性, 即随着新的外星人基地的加入, 计算出到所有外星人基础的最短距离不小于 K 的顶点的数量。如果把外星人的基地看成白色点,其它点看成黑色点。每加入一个基地, 就重新构图,用第 1 题的算法再做一次 BFS。这样做行吗? 基本想法没有错,但我们可以在一些细节上做得更好。 首先,最关键的是我们想到,以第 1 个顶点 V1(外星人基地)为源点做一次最短路算 法后,再以第 2 个顶点 V2 为源点求最短路时,一定不能把最短距离数组 dist[]置为 INF,而

只需要把 dist[V2]=0,然后再以 V2 为源点去松弛其它不是基地的顶点。这样,既避免了多次 memset 操作,也避免了处理多个顶点作为源点的麻烦,更重要的是,每一次最短路算法时, dist 数组元素的初值不再是 INF,收敛到最短距离的速度会快很多,这种情况,使用 SPFA 算 法效率尤高。 但是请注意,尽管 dist[]数组每次不必置为 INF,但 visit[]还是每次都要清 0 的。 其次, 我们要想到, 随着新的基地的加入, 最短距离不小于 K 的顶点数量是单调不增的, 而且一个顶点一旦进入最短距离小于 K 的集合,是不可能再跳出那个集合的。这样,我们可 以维护一个全局变量 ans,它的初值是第 1 次最短路后符合条件的顶点数。在随后的最短路 算法中,只要一个 dist[i]小于 K,就从 ans 中减 1。这样就可以在每次最短路算法后,直接输 出 ans 得解。 参考程序 1:SPFA

第 3 题 无线通讯网
这道题比第 2 题稍好一点,现场 3 人 AC。 其实题意还是挺直白的,就是选择两种通讯方式,使得所有哨所都连通,并且让使用无 线收发器的距离尽可能短。 这道题,因为涉及 2 个变量。可考虑先“屏蔽”其中一个,单独考虑另外一个。当把问 题性质分析清楚后, 再考虑另一个变量的加入, 对问题的影响。 那本题要先屏蔽哪个变量呢? 因为卫星电话的数量是固定的, 而无线电收发器的变化更灵活, 所以挑选收发器更能分析出 问题的性质。 如果不使用卫星电话,要满足“所有哨所连通,并且最远的收发器的距离尽可能短”这 一条件,该怎么做呢?思路有两个: 如果对二分答案特别熟悉,就立即会想到,这又是一个“最大值最小”的问题。接着往 下分析,就会想到,二分收发器的最远距离 D,在任两个相距不大于 D 的哨所之间连边。对 图做一次 DFS,统计连通子图的个数。如果个数不大于卫星电话的线路数 S,则各个子图之 间可通过卫星电话连通。然后继续增大 D 值,再次构图并 DFS,统计子图个数。当子图个数 超过 S 时,就不再合法。这时,使得子图个数不超过 S 的最大 D 值就找出来了。 分析这个算法的时间复杂度。设平面上两点间的最大距离为 MAXD,则二分区间为[0, MAXD]。预处理任两个哨所的距离时间为 O(N^2),把距离存为一个邻接矩阵,DFS 一次的时 间为 O(N^2)。一共要做 logMAXD 次 DFS,所以总时间为 O(N^2*logMAXD)。对于题目所给的 数据范围,完全可以接受。 如果对图算法理解更透彻,则会发现,图的生成树具有把图连通的功能,而最小生成树 的最大边是所有生成树中最大边最小的。 这个性质还可以加强为: 若把生成树的 N-1 条边按 权值排序,则最小生成树的每条边都不大于另一棵生成树。 这样,就可以先用 PRIM 或 KRUSKAL 算法求出一棵最小生成树的 N-1 条边,然后找到第 N-1-S 条边的长度,即是题目所求的 D 值。 参考程序 1:最小生成树算法 参考程序 2:二分答案

第 4 题 又砍树
这是一道异常简单的树 DP 题,甚至都不能称为树 DP 题,只能叫 DFS 的简单应用,因 为它没有转移,只是统计了各个子树的结点个数,然后判断当前结点是否符合条件。 首先读入数据,并构图。因为只需要在这个树形图上做 DFS,所以不用多叉转二叉。用 标准的邻接矩阵存图就可以了。 不过注意, 无向边要存两遍, 所以边结构体数组要开 MAXN*2 的大小。我在 OJ 上交题时,就错了一次。今后一看到无向图,就要提醒自己注意这一点。 然后就是标准的 DFS(int i)。返回以 i 为根的子树的结点总数。当删除结点 i 时,整棵树 被分成了 i 的父结点以上的部分,以及 i 以下的每棵子树部分。根据题意,每个部分的结点 个数都不能超过 n/2。 每棵子树返回的结点数可以在递归时得到, 每枚举一个子结点时, 判断一下返回值就行。 对于 i 的父结点以上的部分,其实也很简单,就是总结点数减去 i 为根的总结点数。 当 i 符合条件后,把它压入一个 vector 类型的变量 ans。递归结束后,对 ans 排序、输 出。 参考程序:DFS 算法


相关文章:
NOIP2012普及组初赛及答案(Pascal)
NOIP2012普及组初赛及答案(Pascal)_学科竞赛_初中教育_教育专区。更新第10题答案...14页 2下载券 08年普及组Pascal答案 1页 免费喜欢此文档的还喜欢 ...
NOIP2012提高组初赛及答案(Pascal)_图文
NOIP2012提高组初赛及答案(Pascal)_学科竞赛_高中教育_教育专区。用了两天的时间...体育比赛中,每一级比赛的优胜者晋级上一级比赛 5.如里不在快速排序中引入随机...
NOIP 图论代码总结
64页 1财富值 NOIp图论算法与模型构建 96页 免费 noip2012信息学奥赛基础模.....图论的一些代码总结图论的一些代码总结隐藏>> 【单源最短路径_dijkstra】 var ...
更多相关标签:
noip 图论 | 图论算法 | 图论科技 | 图论及其算法 | 集合论与图论 | 图论导引 | 图论与代数结构 | 图论及其应用 |