#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<utility>
#include<iomanip>
#include<queue>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))
#define fill(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define pi acos(-1.0)
#define eps 1e-9
int page[100+5][100+5];
vector<int>v;
vector<int>vnode;
map<int,int>mp;
void Floyd_Warshall(int ct)
{
int i,j,k;
for(k=0;k<ct;k++)
for(i=0;i<ct;i++)
for(j=0;j<ct;j++)
page[vnode[i]][vnode[j]]=min(page[vnode[i]][vnode[j]],page[vnode[i]][vnode[k]]+page[vnode[k]][vnode[j]]);
}
int main()
{
int i,j,a,l,l2,tc=1;
double sum,pair;
while(cin>>a)
{
fill(page,10000);
v.clear();
vnode.clear();
mp.clear();
if(a==0)
{
cin>>a;
break;
}
v.PB(a);
while(cin>>a)
{
if(a==0)
{
cin>>a;
break;
}
v.PB(a);
}
l=v.size();
for(i=0;i<l;i+=2)
{
page[v[i]][v[i+1]]=1;
if(mp[v[i]]!=1)
{
mp[v[i]]=1;
vnode.PB(v[i]);
}
if(mp[v[i+1]]!=1)
{
mp[v[i+1]]=1;
vnode.PB(v[i+1]);
}
}
sum=0;
l2=vnode.size();
Floyd_Warshall(l2);
for(i=0;i<l2;i++)
for(j=0;j<l2;j++)
if(i!=j)
//cout<<page[vnode[i]][vnode[j]]<<endl;
sum+=page[vnode[i]][vnode[j]];
//cout<<l2*(l2-1)<<endl;
/*for(i=1;i<=l2;i++)
for(j=1;j<=l2;j++)
if(i!=j)
//cout<<page[i][j]<<endl;
sum+=page[i][j];*/
pair=double(l2*(l2-1));
//cout<<sum/(l2*(l2-1))<<endl;
printf("Case %d: average length between pages = %.3lf clicks\n",tc,sum/pair);
tc++;
}
return 0;
}
No comments:
Post a Comment