UVa 821 Page Hopping

2010-02-22T20:05:00.000+09:00
Floyd 알고리즘을 이용하면 쉽게 풀릴듯..
2000년 ACM World Final 중에서 가장 높은 정답률을 보인 문제
코드
view plaincopy to clipboardprint?
#include <iostream>  
#include <cstdlib>  
#include <list>  
  
using namespace std;  
  
#define INFINITE 1000  
  
unsigned int pageGraph[101][101];  
bool usedPage[101];  
list<unsigned int> usedPageList;  
  
int main()  
{  
    unsigned int pairs[2];  
  
    int count = 1;  
    int sum = 0;  
    float average = 0.0;  
    while( cin >> pairs[0] >> pairs[1])  
    {  
        if(pairs[0] == 0 && pairs[1] == 0)  
        {  
            break;  
        }  
        // graph 초기화  
        for(int i = 0; i < 101; i++)  
        {  
            for(int j = 0; j < 101; j++)  
            {  
                pageGraph[i][j] = INFINITE;  
            }  
        }  
        //memset(pageGraph, , sizeof(pageGraph));  
        memset(usedPage, false, sizeof(usedPage));  
        usedPageList.clear();  
        sum = 0;  
        average = 0.0;  
  
        // graph 생성  
        do{  
            if(pairs[0] == 0 && pairs[1] == 0)  
            {  
                break;  
            }  
            usedPage[pairs[0]] = true;  
            usedPage[pairs[1]] = true;  
            pageGraph[pairs[0]][pairs[1]] = 1;  
              
        }  
        while( cin >> pairs[0] >> pairs[1]);  
  
          
        for(int i= 1; i <= 100; i++ )  
        {  
            if(usedPage[i])  
            {  
                usedPageList.push_back(i);  
            }  
        }  
  
        //floyd algorithm  
        list<unsigned int>::iterator it_i, it_j, it_k;  
        for(it_i = usedPageList.begin(); it_i != usedPageList.end(); ++it_i)  
        //it_i를 거쳐서 가는경우  
        {  
            for(it_j = usedPageList.begin(); it_j != usedPageList.end(); ++it_j)  
            {  
                for(it_k = usedPageList.begin(); it_k != usedPageList.end(); ++it_k)  
                {  
                    if(pageGraph[*it_j][*it_i] != INFINITE && pageGraph[*it_i][*it_k] != INFINITE  
                        && *it_j != *it_i && *it_k != *it_i && *it_j != *it_k)  
                    {  
                        if(pageGraph[*it_j][*it_i] + pageGraph[*it_i][*it_k] < pageGraph[*it_j][*it_k])  
                        {  
                            pageGraph[*it_j][*it_k] = pageGraph[*it_j][*it_i] + pageGraph[*it_i][*it_k];  
                        }  
                    }  
                      
                }  
            }  
        }  
  
        for(it_i = usedPageList.begin(); it_i != usedPageList.end(); ++it_i)  
        {  
            for(it_j = usedPageList.begin(); it_j != usedPageList.end(); ++it_j)  
            {  
                if(pageGraph[*it_i][*it_j] != INFINITE)  
                {  
                    sum += pageGraph[*it_i][*it_j];  
                }  
            }  
        }  
  
        average = (float)sum / (usedPageList.size()*(usedPageList.size()-1));  
        printf("Case %d: average length between pages = %.3f clicks\n",  
                count, average);  
        count++;  
    }  
  
    return 0;  
}  
dungfly

UVa 821 Page Hopping
