Saturday 5 May 2012

UVa 821 Page Hopping Solution

#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