《图的遍历》练习

《《图的遍历》练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《图的遍历》练习1、珍珠（bead）【问题描述】有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间。即在所有珍珠的重量重，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法：给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。例如：下列给出对5颗珍珠进行四次比较的情况：(1)珍珠2比珍珠1重(2)珍珠4比珍珠3重(3)珍珠5比珍珠1重(4)珍珠4比珍珠2重根据以上结果，虽然我们不能精确地找出哪个珍珠具有中间重量，但是我们可

2、以肯定珍珠1和珍珠4不可能具有中间重量，因为珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4轻，所以我们可以移走这两颗珍珠。写一个程序统计出共有多少颗珍珠肯定不会有中间重量。【输入格式】输入文件第1行包含两个用空格隔开的整数N(1<=N<=99)和M，且N为奇数，M表示对珍珠进行的比较次数，接下来的M行每行包含两个用空格隔开的整数x和y，表示珍珠x比珍珠y重。【输出格式】输出文件仅一行，包含一个整数，表示不可能是中间重量的珍珠的总数【样例输入】5421435142【样例输出】22、铲雪车（snow）【问题描述】随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是

3、双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？【输入格式】输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20km/h，不铲雪时前进速度为50km/h。保证：铲雪车从起点一定可以到达任何街道。【输出格式】铲掉所有街道上的

4、雪并且返回出发点的最短时间，精确到分种。【输入样例】1000010000100005000-100005000100005000100001000010000【输出样例】3:55【注解】3小时55分钟3、骑马修栅栏（fence）【问题描述】农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John是一个和其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用

5、1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看出是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个(也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的...)。输入数据保证至少有一个解。【输入格式】第1行：一个整数F(1<=F<=1024)，表示栅栏的数目。第2到F+1行：每行两个整数i,j(1<=i,j<=500)，表示这条栅栏连接i与j号顶点。【输出格式】

6、对于每组数据输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的第一组解是认为正确的。【样例输入】9122334424525565746【样例输出】12342546574、邮递员（carrier）【问题描述】邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那些遥远乡村的所有村子和小鹿至少一次的邮路（输入数据将会保证这么一条路是一定存在的）。但是，每条路线都是有一个花费的。各个村子里的村民希望邮递员到达他们村子的时间越早越好。因此，各个村子里的人们采用了一些措施：假设第i号村子是邮递员在他的邮递路线上到达的第k个村子。如果k<=w（i），

7、那么这个村子的村民就会付给邮局w(i)-k欧元。当然，如果k>w（i），邮局也同意付w(i)-k欧元给这个村子，对某些村子重复经过要重复收费。此外，邮递员每经过一条小路，邮局也要付给邮递员1欧元作为补贴。现在有n个村子，编号依次为1到n。邮局就位于1号村子，因此邮递员的传递路线从这里开始，也从这个村子结束。能够离开每个存在的路口的数目一定是2,4或者8。这里允许出现同样的村子间存在多条小路，或者某条小路构成了一个自环的情