当前位置:首页 > 数据结构 > 二叉树 > 正文
SSOJ2463医院设置(换根法、洛谷P1364)
263+

题目大意:二叉树中,结点i有$a_i$人,每条边长1米,大家需要去某个结点集合,选哪个结点大家走的距离最小?最小值是多少?

题目描述

设有一棵二叉树(如下图),其中圈中的数字表示结点中居民的人口,圈边上数字表示结点编号。现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻结点之间的距离为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

解题思路

方法一:枚举医院位置,并以他为根,通过搜索计算距离和,打擂台求最小值。

方法二:预处理出以根为医院的距离和,用先序遍历,用根递推出儿子的距离和。

程序实现

树中的结点路径是唯一的,所以不需要重复搜索,搜过记下来下次return,每次搜索复杂度是O(n)。

与普通搜索不一样的是,迷宫是4个、8个方向,二叉树则是3个方向:左儿子、右儿子、父亲,都可以走过去。

在搜索过程中,记录每个结点的深度(边数),就可以求出该节点到医院的距离之和。

以结点1为根:总路程是136,那么换根为右儿子,产生什么变化?

不妨设,原来全部人(z个)都跑去结点1看病,一共走了136km;现在,医院改在结点3,大家不需要去结点1,只需要去结点3(子树人数是s),那么:

1、结点1和2的人(z-s),需要再跑1km,距离增加z-s

2、结点3、4、5的人(s),之前跑远了,他们现在可以少跑1km,距离减少s

那么换根造成距离之和的编号是z-s – s,每次换根都可以用这种方法!

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2463医院设置(换根法、洛谷P1364):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter