UVa 821 Page Hopping

题目描述给定一个有向图节点编号在111到100100100之间。图是强连通的任意节点到任意其他节点均有路径。要求计算所有节点对之间的最短路径长度的平均值。输入包含多个测试用例每个测试用例以若干条有向边a b描述以0 0结束。所有测试用例结束后还有一个0 0。输入格式输入包含多个测试用例。每个测试用例由若干行组成每行两个整数a,ba, ba,b表示从aaa到bbb的有向边。每个测试用例以0 0结束。整个输入以0 0结束。输出格式对于每个测试用例输出一行格式为Case x: average length between pages avg clicks其中avgavgavg精确到三位小数。样例输入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样例输出Case 1: average length between pages 1.833 clicks Case 2: average length between pages 1.750 clicks题目分析给定有向图节点数最多100100100。需要计算所有节点对i≠ji \ne jij的最短路径长度之和除以节点对数n×(n−1)n \times (n-1)n×(n−1)。由于节点数小可使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算所有节点对之间的最短路径。注意图是强连通的因此所有距离均为有限值。解题思路实现步骤确定如下步骤1\texttt{1}1. 初始化距离矩阵dist[i][j]∞\textit{dist}[i][j] \inftydist[i][j]∞i≠ji \ne jijdist[i][i]0\textit{dist}[i][i] 0dist[i][i]0。步骤2\texttt{2}2. 读入边直到0 0。动态记录出现的节点编号压缩为111到nnn的连续编号便于矩阵大小固定。对每条有向边(u,v)(u, v)(u,v)设置dist[id[u]][id[v]]1\textit{dist}[id[u]][id[v]] 1dist[id[u]][id[v]]1。步骤3\texttt{3}3. 使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算所有点对最短路径dist[i][j]min⁡(dist[i][j],dist[i][k]dist[k][j]) \textit{dist}[i][j] \min(\textit{dist}[i][j], \textit{dist}[i][k] \textit{dist}[k][j])dist[i][j]min(dist[i][j],dist[i][k]dist[k][j])步骤4\texttt{4}4. 统计所有i≠ji \ne jij的dist[i][j]\textit{dist}[i][j]dist[i][j]之和除以n×(n−1)n \times (n-1)n×(n−1)得到平均值。步骤5\texttt{5}5. 输出结果保留三位小数。由于输入边可能重复但距离取最小值不影响结果。节点编号范围111到100100100可直接使用100×100100 \times 100100×100矩阵。代码实现// Page Hopping// UVa ID: 821// Verdict: Accepted// Submission Date: 2016-12-02// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,from,to;intclicks[110][110],number[110],n;while(cinfromto,from0){coutCase cases: average length between pages ;for(inti1;i100;i)for(intj1;j100;j)clicks[i][j]100000;memset(number,0,sizeof(number));n0;do{if(!number[from])number[from]n;if(!number[to])number[to]n;clicks[number[from]][number[to]]1;}while(cinfromto,from0);for(inti1;in;i)clicks[i][i]0;// Floyd-Warshallfor(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)if(clicks[i][j]clicks[i][k]clicks[k][j])clicks[i][j]clicks[i][k]clicks[k][j];inttotalClicks0;for(inti1;in;i)for(intji1;jn;j){totalClicksclicks[i][j];totalClicksclicks[j][i];}doubleaverageClicks(double)totalClicks/(double)(n*n-n);coutfixedsetprecision(3)averageClicks clicks\n;}return0;}总结本题通过Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法在O(n3)O(n^3)O(n3)时间内计算所有点对最短路径n≤100n \le 100n≤100运行时间可接受。注意输入以0 0结束且每个测试用例内也以0 0分隔。节点编号需要压缩以简化矩阵操作。平均值计算时分母为n×(n−1)n \times (n-1)n×(n−1)因为有向图中节点对有序。该解法清晰高效是计算平均最短路径长度的典型方法。