网页跳跃 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) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA821/64a126777dbd33365e10b8e85f175d740b03a017.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA821/dc56bd7cbe2df86c183ad3208d07f07b347c8973.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA821/00bbc0be2b457dd1728f0ab86a1397a07e93c376.png)

输入输出样例

输入样例 #1

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

输出样例 #1

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