1338：【例3-3】医院设置
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
设有一棵二叉树（如下图），其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2×20+2×40=136；若医院建在3处，则距离和=4×2+13+20+40=81……
【输入】
第一行一个整数n，表示树的结点数（n≤100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接，为0表示无链接。
【输出】
一个整数，表示最小距离和。
【输入样例】
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
【输出样例】
81
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. int n,vis[110],ans=0x7fffffff; 7. struct Node{ 8. int data; 9. int father,left,right; 10. }t[110]; 11. int cal(int x,int d){ 12. if(x==0||vis[x]==1) return 0; 13. vis[x]=1; 14. int left=cal(t[x].left,d+1); 15. int right=cal(t[x].right,d+1); 16. int father=cal(t[x].father,d+1); 17. return left+right+father+t[x].data*d; 18. } 19. int main() 20. { 21. cin>>n; 22. for(int i=1;i<=n;i++) 23. cin>>t[i].data>>t[i].left>>t[i].right; 24. for(int i=1;i<=n;i++){ 25. t[t[i].left].father=i; 26. t[t[i].right].father=i; 27. } 28. //for(int i=1;i<=n;i++) 29. // cout<<i<<" "<<t[i].father<<" "<<t[i].left<<" "<<t[i].right<<endl; 30. for(int i=1;i<=n;i++){ 31. memset(vis,0,sizeof(vis)); 32. int temp=cal(i,0); 33. // cout<<i<<" "<<temp<<endl; 34. ans=min(ans,temp); 35. } 36. cout<<ans<<endl; 37. return 0; 38. }
