MYF

UVa 821 Page Hopping

Posted on | In | | Visitors

题目链接

UVa 821

方法：最短路水题 Floyd-Warshall

题目分析

题目大意

uva821
先介绍一个概念，如图所示，有1,2,3,4四个网站，对于每一个箭头，如1→2，表示从网站1可以直接跳转到网站2，那么，从1到3，有两种方式，①1→2→4→3，②1→3，方法①需要跳转三次，方法②跳转1次，显然，从1到3的最少跳转次数是1，其他同理。

那么，给定n个网站的，如果这n个网站中，可以从u跳转到v，每次产生一个跳转次数t，假设可以建立cnt个这种关系，求平均最小跳转次数(期望)，也就是求∑ti/cnt。

解析

由于数据量较小(最多100)，并且是多源的，故不能采用dijkstra算法，最简单易行的当属
Floyd-Warshall算法，先全部赋一个比较大的值(INF)，然后跑一遍Floyd，再把这个数组遍历一遍，如果mp[u][v]!=INF，则表示u→v是可以走得通的，mp[u][v]记录从u到v的最少跳转次数。累加这些求平均值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int mp[105][105];
int u,v,cas=1;
int main(){
    while (scanf("%d%d",&u,&v),u+v) {
        
        for (int i=1; i<105; i++)
            for (int j=1; j<105; j++)
                mp[i][j]=9999;
        
        mp[u][v]=1;
        int sum=0;
        int t=0;
        int n=max(u, v);
        
        while (scanf("%d%d",&u,&v),u+v) {
            mp[u][v]=1;
            n=max(n, max(u, v));
        }
        
        for (int k=1; k<=n; k++)
            for (int i=1; i<=n; i++)
                for (int j=1; j<=n; j++)
                    if (mp[i][j]>mp[i][k]+mp[k][j])
                        mp[i][j]=mp[i][k]+mp[k][j];
        
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                if (i!=j&&mp[i][j]!=9999) {
                    sum+=mp[i][j];
                    t++;
                }
        
        printf("Case %d: average length between pages = %.3f clicks\n",cas++,1.0*sum/t);
    }
    
}