UVA821 Page Hopping 解题报告

本文主要是介绍UVA821 Page Hopping 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA821 Page Hopping 解题报告

题目链接

https://vjudge.net/problem/UVA-821

题目大意

最近的研究表明，互联网上任何一个网页在平均情况下最多只需要单击19次就能到达任意一个其他网页。如果把网页看成一个有向图中的结点，则该图中任意两点间最短距离的平均值为19。输入一个n（1≤n≤100）个点的有向图，假定任意两点之间都相互到达，求任意两点间最短距离的平均值。输入保证没有自环。

解题思路

建模为边权为1的图，然后就是标准的floyd模板，注意处理一下自环边的问题即可，细节见代码注释。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define endl '\n';
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;
int G[maxn][maxn];void init() {for (int i = 1; i <= 100; i++)for (int j = 1; j <= 100; j++)G[i][j] = INF;
}void floyd() {for (int k = 1; k <= 100; k++)for (int i = 1; i <= 100; i++)for (int j = 1; j <= 100; j++)if (G[i][k] != INF && G[k][j] != INF)   // 没有自环边，这里的多源最短路处理过程中会更新自环的距离G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}void solve() {int u, v, kase = 0;while (cin >> u >> v, u) {kase++;init();G[u][v] = 1;while (cin >> u >> v, u) {G[u][v] = 1;}floyd();// 求均值double ans = 0;int cnt = 0;for (int i = 1; i <= 100; i++) {for (int j = 1; j <= 100; j++) {      // 无向图，所以不能是j = i + 1if (i != j && G[i][j] != INF) {     // 没有自环边cnt++;ans += G[i][j];}   }}ans /= cnt;cout << "Case " << kase << ": average length between pages = "<< setprecision(3) << ans << " clicks\n";}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);int Case = 1;// cin >> Case;while (Case--)solve();return 0;
}