《图遍历》练习.pdf

《图的遍历》练习 1、珍珠（bead） 【问题描述】 有n 颗形状和大小都一致的珍珠，它们的重量都不相同。n 为整数，所有的珍珠从1 到n 编号。你的任务是发现哪颗珍珠的重量刚好处于正中间。即在所有珍珠的重量重，该 珍珠的重量列(n+1)/2 位。下面给出将一对珍珠进行比较的办法： 给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一 系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。 例如：下列给出对5 颗珍珠进行四次比较的情况： (1)珍珠2 比珍珠1 重 (2)珍珠4 比珍珠3 重 (3)珍珠5 比珍珠1 重 (4)珍珠4 比珍珠2 重 根据以上结果，虽然我们不能精确地找出哪个珍珠具有中间重量，但是我们可以肯定 珍珠1 和珍珠4 不可能具有中间重量，因为珍珠2、4 、5 比珍珠1 重，而珍珠1、2、3 比 珍珠4 轻，所以我们可以移走这两颗珍珠。 写一个程序统计出共有多少颗珍珠肯定不会有中间重量。 【输入格式】 输入文件第 1 行包含两个用空格隔开的整数 N(1=N=99)和 M，且N 为奇数，M 表示 对珍珠进行的比较次数，接下来的M 行每行包含两个用空格隔开的整数x 和y ，表示珍珠x 比珍珠y 重。 【输出格式】 输出文件仅一行，包含一个整数，表示不可能是中间重量的珍珠的总数 【样例输入】 5 4 2 1 4 3 5 1 4 2 【样例输出】 2 2、铲雪车（snow） 【问题描述】 随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路 都是双车道，因为城市预算的削减，整个城市只有1 辆铲雪车。铲雪车只能把它开过的地 方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的 街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？ 【输入格式】 输入数据的第1 行表示铲雪车的停放坐标（x,y ），x ，y 为整数，单位为米。下面最 多有100 行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是 双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U 型弯。 铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h 。 保证：铲雪车从起点一定可以到达任何街道。 【输出格式】 铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。 【输入样例】 1 0 0 0 0 10000 10000 5000 -10000 5000 10000 5000 10000 10000 10000 【输出样例】 3:55 【注解】 3 小时55 分钟 3、骑马修栅栏（fence） 【问题描述】 农民John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John 是一个和其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。 你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好 被经过一次。John 能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。 每一个栅栏连接两个顶点，顶点用1 到500 标号(虽然有的农场并没有500 个顶点)。一 个顶点上可连接任意多(=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到 达另外的所有栅栏)。 你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示) 。我们如果把输出的路 径看出是一个500 进制的数，那么当存在多组解的情况下，输出500 进制表示法中最小的一 个(也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的...)。输入数据保证 至少有一个解。 【输入格式】 第1 行：一个整数F(1=F=1024)，表示栅栏的数目。 第2 到F+1 行：每行两个整数i,j(1=i,j=500)，表示这条栅栏连接i 与j 号顶点。 【输出格式】 对于每组数据输出应当有 F+1 行，每行一个整数，依次表示路径经过的顶点号。