申請SAE

如果您發現本博客的外觀很難看,那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致!
請翻~牆!

我的Wordpress博客的地址: http://zhuyf.tk/

2011年11月1日 星期二

[最短路]OI練習題:醫院設置 hospital

 信息學競賽練習題:醫院設置(hospital)

【問題描述】
設有一棵二叉樹,如圖 5-1 :
其中,圈中的數字表示結點中居民的人口。圈邊上數字表示結點編號,現在要求在某個結點上建立一個醫院,使所有居民所走的路程之和爲最小,同時約定,相鄰接點之間的距離爲 1 。
如上圖中,若醫院建在:
1 處,則距離和 =4+12+2*20+2*40=136
3 處,則距離和 =4*2+13+20+40=81

【輸入】
第一行一個整數 n ,表示樹的結點數。 (n ≤ 100)
接下來的 n 行每行描述了一個結點的狀況,包含三個整數,整數之間用空格 ( 一個或多個 ) 分隔,其中:第一個數爲居民人口數;第二個數爲左鏈接,爲 0 表示無鏈接;第三個數爲右鏈接。

【輸出】
一個整數,表示最小距離和。

【樣例】
hospital.in
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
hospital.out
81

【分析】
這是最短路徑問題,可以用Floyd算法求出。
由於相鄰兩點之間的距離為1,所以任意兩地之間的距離等於這兩地之間 間隔 的節點個數+1。

可以把任意兩點之間的距離初始化為-1,把同一地點的距離初始化為0。
即:mat[i][j]=-1(i!=j) ;mat[i][i]=0。
然後用Floyd算法求出任意兩點之間的最短路。

最後枚舉 最小的總路程即可。

【我的代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int mat[101][101];
int People[101];
int N;

void Floyd()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
        { 
            for(int j=1;j<=N;j++) 
            { 
                if ( mat[i][k]!=-1 && mat[k][j]!=-1) 
                { 
                    temp=mat[i][k]+mat[k][j];
                    if ( (mat[i][j]==-1) || ( mat[i][j]>temp ) ) 
                        mat[i][j]=temp; 
                } 
            } 
        } 
    } 
}

void init()
{
    scanf("%d\n",&N);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            mat[i][j]=-1;
   
    for(int i=1;i<=N;i++)
        mat[i][i]=0;
   
    int l,r,p;
    for (int i=1;i<=N;i++)
    {
        scanf("%d %d %d\n",&p,&l,&r);
        mat[i][r]=1;
        mat[i][l]=1;
        mat[r][i]=1;
        mat[l][i]=1;
        People[i]=p;
    }
    return;
}

void Work()
{
    int Min=0x7fffffff;
    int Tmp=0;
    for (int i=1;i<=N;i++)
    {
        Tmp=0;
        for (int j=1;j<=N;j++)
        {
            Tmp+=(mat[i][j]*People[j]);
        }
        if(Tmp<Min)
            Min=Tmp;
    }
    cout<<Min<<endl;
}

int main()
{
    freopen("hospital.in","r",stdin);
    freopen("hospital.out","w",stdout);
    init();
    Floyd();
    Work();
    return 0;
}

沒有留言:

張貼留言