2396 - 医院设置
设有一棵二叉树（如图3-8，其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2*20+2*40=136；若医院建在3处，则距离和=4*2+13+20+40=81……
<br />
<br />
Input
输入第一行一个整数n，表示树的结点数（n<=100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接，为0表示无链接。
Output
输出一个整数，表示最小距离和。
Examples
Input
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
Output
81
Hint
数据规模也不大，采用邻接矩阵存储，用Floyed法求出任意两结点之间的最短路径长，然后穷举医院可能建立的n个结点位置
Solution C++
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<iomanip> #define MAX 1000000 using namespace std; int n,x,y,tot=0,ans=0x7fffffff; int p[101]; int g[101][101]={0}; void in(); void out(); void flod(); void find(); int main() { //freopen("3.in","r",stdin); in(); flod(); find(); out(); return 0; } // void in() { cin>>n; n++; for (int i=1;i<n;i++) { g[i][i]=0; for (int j=1;j<n;j++) { if (i==j) { continue; } if (g[i][j]) { continue; } g[i][j]=MAX; } cin>>p[i]>>x>>y; if (x>0) { g[i][x]=g[x][i]=1; } if (y>0) { g[i][y]=g[y][i]=1; } } } // void flod() { for (int i=1;i<n;i++) { for (int j=1;j<n;j++) { if (j==i)// || g[i][j]==MAX { continue; } for (int k=1;k<n;k++) { /*if (g[k][j]==MAX) { continue; }*/ if ((k!=j) && (k!=i) && (g[i][j]+g[j][k]<g[i][k])) { g[i][k]=g[i][j]+g[j][k]; } } } } } // void find() { for (int i=1;i<n;i++) { tot=0; for (int j=1;j<n;j++) { if (g[i][j]==MAX) { continue; } tot+=g[i][j]*p[j]; } if (tot<ans) { ans=tot; } } } // void out() { cout<<ans<<endl; }
Hint
数据规模也不大，采用邻接矩阵存储，用Floyed法求出任意两结点之间的最短路径长，然后穷举医院可能建立的n个结点位置