【問題描述】
設有一棵二叉樹,如圖 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;
}
#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;
}
沒有留言:
張貼留言