首页 > 代码库 > 洛谷P1364 医院设置(Floyd)
洛谷P1364 医院设置(Floyd)
题目描述
设有一棵二叉树,如图:
其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻接点之间的距离为l。如上图中,
若医院建在1 处,则距离和=4+12+2*20+2*40=136;若医院建在3 处,则距离和=4*2+13+20+40=81……
输入输出格式
输入格式:第一行一个整数n,表示树的结点数。(n≤100)
接下来的n行每行描述了一个结点的状况,包含三个整数,整数之间用空格(一个或多个)分隔,其中:第一个数为居民人口数;第二个数为左链接,为0表示无链接;第三个数为右链接。
输出格式:一个整数,表示最小距离和。
输入输出样例
输入样例#1:
5 13 2 34 0 012 4 520 0 040 0 0
输出样例#1:
81
本来是想刷一下树形结构的题目,结果这题赤裸裸Floyd啊!计算 出两点间最小距离,然后枚举医院的设置点,取最小就行了。
代码如下:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 #define inf 0x3f3f3f3f 5 int hspt[110][110],num[110],n,x,y; 6 int main() 7 { 8 //freopen("de.txt","r",stdin); 9 scanf("%d",&n);10 int ans=inf;11 memset(hspt,inf,sizeof hspt);12 for (int i=1;i<=n;++i)13 {14 scanf("%d%d%d",&num[i],&x,&y);15 hspt[x][i]=1;16 hspt[i][x]=1;17 hspt[y][i]=1;18 hspt[i][y]=1;19 }20 for (int k=1;k<=n;++k)//Floyd算法21 for (int i=1;i<=n;++i)22 for (int j=1;j<=n;++j)23 if (i!=j&&j!=k)24 hspt[i][j]=min(hspt[i][j],hspt[i][k]+hspt[k][j]);25 for(int i=1;i<=n;++i)26 {27 int tot=0;28 for (int j=1;j<=n;++j)29 {30 if (i!=j)31 tot+=hspt[i][j]*num[j];32 }33 ans=min(ans,tot);34 }35 printf("%d\n",ans);36 return 0;37 }
洛谷P1364 医院设置(Floyd)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。