【題目描述】

設(shè)有一棵二叉樹（如圖3-8，其中圈中的數(shù)字表示結(jié)點中居民的人口，圈邊上數(shù)字表示結(jié)點編號?，F(xiàn)在要求在某個結(jié)點上建立一個醫(yī)院，使所有居民所走的路程之和為最小，同時約定，相鄰結(jié)點之間的距離為1。就本圖而言，若醫(yī)院建在1處，則距離和=4+12+2*20+2*40=136；若醫(yī)院建在3處，則距離和=4*2+13+20+40=81…

【輸入】

第一行一個整數(shù)n，表示樹的結(jié)點數(shù)（n≤100）。接下來的n行每行描述了一個結(jié)點的狀況，包含三個整數(shù)，整數(shù)之間用空格（一個或多個）分隔，其中：第一個數(shù)為居民人口數(shù)；第二個數(shù)為左鏈接，為0表示無鏈接；第三個數(shù)為右鏈接，為0表示無鏈接。

【輸出】

一個整數(shù)，表示最小距離和。

【輸入樣例】

5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

【輸出樣例】

81

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 101 #define MOD 123 #define E 1e-6 using namespace std; int a[N][N],b[N],sum[N]; int main() {int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)a[i][j]=0;elsea[i][j]=INF;}}for(int i=1;i<=n;i++){int left,right;cin>>b[i]>>left>>right;if(left!=0)a[i][left]=a[left][i]=1;if(right!=0)a[i][right]=a[right][i]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];int minn=INF;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)sum[i]+=a[i][j]*b[j];if(sum[i]<minn)minn=sum[i];}cout<<minn<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的医院设置（信息学奥赛一本通-T1338）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。