時(shí)間限制: 1000 ms 內(nèi)存限制: 65536 KB
提交數(shù): 1018 通過數(shù): 719

【題目描述】

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

【輸入】

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

【輸出】

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

【輸入樣例】

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

【輸出樣例】

81

【來源】

No

算法分析

這是一道簡單的二叉樹應(yīng)用問題，問題中的節(jié)點(diǎn)數(shù)并不多，數(shù)據(jù)規(guī)模也不大，采用鄰接矩陣存儲(chǔ)，用Floyed求出任意兩節(jié)點(diǎn)之間的最短路徑，然后窮舉醫(yī)院可能建立的n個(gè)節(jié)點(diǎn)位置找出一個(gè)最小距離的位置即可。

當(dāng)然也可以用雙鏈表結(jié)構(gòu)或帶父節(jié)點(diǎn)信息的數(shù)組存儲(chǔ)結(jié)構(gòu)來解決，但實(shí)際操作稍微麻煩了一點(diǎn)。

代碼

#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int a[101]; int g[101][101]; int main () {int n,i,j,k,l,r,min,total;cin>>n;for(i=1;i<=n;i++){for(j=1;j<=n;j++){g[i][j]=1000000;}}for(i=1;i<=n;i++){g[i][j]=0;cin>>a[i]>>l>>r;if(l>0) g[i][l]=g[l][i]=1;if(r>0) g[i][r]=g[r][i]=1;}for(k=1;k<=n;k++){for(i=1;i<=n;i++){if(i!=k){for(j=1;j<=n;j++){if(i!=j&&k!=j&&g[i][k]+g[k][j]<g[i][j]){g[i][j]=g[i][k]+g[k][j];}}}}}min=0x7fffffff;for(i=1;i<=n;i++){total=0;for(j=1;j<=n;j++){total+=g[i][j]*a[i];}if(total<min) min=total;}cout<<min<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（C++）在线评测系统——基础（三）数据结构—— 1338：【例3-3】医院设置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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