WUSTOJ1654医院设置

1654: 医院设置 Time Limit: 1 Sec  Memory Limit: 65535 MB   64bit IO Format: %lld Description 一颗二叉树有n（1≤n≤50）个结点，分别编号为1到n，每个结点代表一个居民点，每个居民点都有一定数量的居民（≤100）。现在需要选择一个居民点建一家医院，使得所有居民走的路程之和最小。同时约定，相邻两节点之间的距离为1。 例如对于样例，有5个居民点，每个居民点的居民数量分别为13，4，12，20，40.如果选择居民点1作为医院位置的话，则距离和为4*1+13*0+12*1+20*2+40*2=136；若选择居民点3的话，则距离和为4*2+13*1+12*0+20*1+40*1=81，… Input 包含多组测试数据。每组测试数据第一行包含一个整数n，接下来的n行，每行3个数据，表示居民点i（1≤i≤n）的居民数和相邻两个居民点编号，如果编号为0表示不存在。 Output 输出最小距离和。 Sample Input     5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 Sample Output 81 中文题目，一般人都是用二叉树来做。

后来发现这道题目的数据范围很小，可以用Floyd算法求的任意两点间的距离，暴力一下就可以过。

#include<iostream> #include<cstdio> #include<cstring> #include<functional> #include<algorithm> #define inf 0x3f3f3f3f #define maxn 105 using namespace std; int n,m,ans; int maps[maxn][maxn]; int num[maxn]; void init() { int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) maps[i][j]=0; else maps[i][j]=inf; } void floyd() { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(maps[i][j]>maps[i][k]+maps[k][j]) maps[i][j]=maps[i][k]+maps[k][j]; int main() { int i,j,a,b,c; while(scanf("%d",&n)!=EOF) { init(); for(i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); num[i]=a; maps[i][b]=1;//无向图 maps[b][i]=1; maps[i][c]=1; maps[c][i]=1; } floyd();//求任意两点间最短距离 int sum; ans=inf; for(i=1;i<=n;i++)//暴力枚举下每一种情况 { sum=0; for(j=1;j<=n;j++) sum+=(num[j]*maps[i][j]); ans=min(ans,sum); } printf("%d\n",ans); } }