网页跳跃 Page Hopping

Page Hopping（网页跳转,uva821） ## 题目描述 最近研究表明，互联网上任何一个网页平均只需要点击19次就可以跳转到任意一个其他网页。如果把互联网上的网页看成一个图中的节点，则该图中任意两点间最短距离的平均值是19. 给定一个图，任意两点之间都相互到达，你的任务是找到任意两点间最短距离的平均值。 例如，下图中，链接显示为有向边，因为从网页a到网页b的链接并不表示能从网页b到网页a。 节点1到节点2,3,4的最短距离分别是1,1,2; 节点2到节点1,3,4的最短距离分别是3,2,1; 节点3到节点1,2,4的最短距离分别是1,2,3; 节点4到节点1,2,3的最短距离分别是2,3,1; 这些路径的和是1+1+2+3+2+1+1+2+3+2+3+1=22，一共有22个节点对，所以节点间的平均距离是22/12，保留三位小数结果是1.833. #### 输入格式 输入包含多组测试数据。 对于每组测试数据，输出一行，包含任意数量的整数对，a和b，a和b之间用一个空格隔开，表示从网页a跳到网页b的链接，整数的范围是1到100。数据对与数据对之间用两个空格隔开，每组测试数据的结尾是“0 0”，表示这这组测试数据结束。 当输入为一行“0 0”时，表示输入文件结束。 输入没有自环，任意两点之间都相互到达。 #### 输出格式 对于每组测试用例输出一行，输出格式为“Case X: average length between pages = Y clicks”,其中X表示测试用例的编号，从1开始，Y表示最短距离的平均值，结果保留3位小数。 ### 输入输出样例 输入样例 1： 1 2 2 4 1 3 3 1 4 3 0 0 1 2 1 4 4 2 2 7 7 1 0 0 0 0 输出样例 1： Case 1: average length between pages = 1.833 clicks Case 2: average length between pages = 1.750 clicks

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=762 [PDF](https://uva.onlinejudge.org/external/8/p821.pdf) 



12 24 13 31 43 00
12 14 42 27 71 00
0 0

Case 1: average length between pages = 1.833 clicks
Case 2: average length between pages = 1.750 clicks