|
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <string.h> #include <stdio.h> #include <map> #define INF 1000000000 using namespace std; map<int,int> m; int graph[105][105]; int sum[105]; double total; int main() { int a,b,cnt; int kase =1; while(cin>>a) { cin>>b; if(a==0 && b==0) break; for(int i=1;i<101;i++) { sum[i]=0; for(int j=1;j<101;j++) { graph[i][j]=INF; if(i==j) graph[i][j]=0; } } cnt=1; m.clear(); m[a]=cnt; if(m[b]==0) { cnt+=1; m[b]=cnt; } graph[m[a]][m[b]]=1; while(cin>>a) { cin>>b; if(a==0 && b==0) break; if(m[a]==0) { cnt+=1; m[a]=cnt; } if(m[b]==0) { cnt+=1; m[b]=cnt; } graph[m[a]][m[b]]=1; } int len = m.size(); for(int k=1;k<=len;k++) { for(int i=1;i<=len;i++) { for(int j=1;j<=len;j++) { if(graph[i][j]>(graph[i][k]+graph[k][j])) graph[i][j] = (graph[i][k]+graph[k][j]); } } } total = 0; for(int i=1;i<=len;i++) { for(int j=1;j<=len;j++) { sum[i]+=graph[i][j]; } total+=sum[i]; } //cout<<"t = "<<total<<"\n"; //cout<<"len ="<<len*(len-1)<<"\n"; total/=(len*(len-1)); cout<<"Case "<<kase++<<": average length between pages = "; printf("%.3lf",total); cout<<" clicks\n"; } return 0; } |