Walls解题报告.pptVIP

IOI 2000 Walls 解题报告 报告人：施澍 2003.7.2 题意简介 城市、空地、俱乐部、城墙 规模： 城市 n =200 空地 m=250 俱乐部 l=30 题意简介 求一块空地i，使从所有俱乐部到i所不得不翻越的城墙数最少。 最优路径+最优方案  问题 如果有多个解，任意输出一个 输入输出 空地 M 城市 N 俱乐部 L L个俱乐部分别所在的城市 接下来有2*M行，每两行对应一个空地，第一行表示空地周围的城市数，第二行表示城市的代号 输入输出 第一行输出总共需要翻越的城墙数 第二行输出达到最优的地点 思维线索 从一个空地到另一个空地，需要翻越一座城墙，而需要求从A地到B地，最少需要翻越的城墙的数目——图论中最短路径问题 确定结点和边 实现算法 构造无向图 用floyd算法求出任意两点间的最短路径 有哪些信誉好的足球投注网站每个空地，从俱乐部到该空地的距离和设为S，求出S最小的空地，输出结果 具体实现——构造图 需要找出结点与结点之间的相邻关系，即哪 空地之间是用城墙分开的。 方法一：记录下每块空地的城墙，当处理一块空地的时候，每处理一段城墙则有哪些信誉好的足球投注网站其他所有空地的城墙，如果相同的则认为那两块空地相邻 O（（MN）2） 方法二：由于任何城墙只可能隔开两块空地，即任一城墙只可能出现在两块空地里，可以记录城墙出现的次数，记录两次则让两块空地相邻 O（MN） 具体实现——floyd算法 经典算法 O（M3） for (k=0;kn;k++) for (i=0;in;i++) for (j=0;jn;j++) if (G[i][k]+G[k][j]G[i][j]) G[i][j]=G[i][k]+G[k][j]; //k是最外层的循环！！！ 具体实现——确定最优地点 因为俱乐部是在城市里，可以选择从城市周围的任何一块空地出发，所以要记录城市和哪些空地相连；计算路径时要选择相邻空地中到目的地的最短距离为俱乐部到目的地的距离 由于俱乐部彼此间是独立的，一个俱乐部的路径的选择不会影响到别的俱乐部的路径选择，所以分别选取最小值即可 算法复杂度 构造图 MN Floyd M3 有哪些信誉好的足球投注网站最优 M（每块空地）*L（每个俱乐部）*M（每个俱乐部可能相邻的空地） 总的时间复杂度O（M3） 其他 算法简单，比较容易联想到用图论来解 预处理比较麻烦，选择适当的数据结构 编程简单，数据也容易过 联想 jol上的1066 treasure hunt好像还要难一点…… * * 1 2 4 3 6 5 10 8 7 9 1 2 4 3 6 5 10 8 7 9 10 10 3 3 6 9 3 1 2 3 3 1 3 7 4 2 4 7 3 3 4 6 7 3 4 8 6 3 6 8 7 3 4 5 8 4 7 8 10 9 3 5 10 8 7 7 9 10 5 4 2 1 1 2 4 3 6 5 10 8 7 9 数字表示空地的标号 包括外围的空地 1 2 7 4 6 5 3 8 9 10 *