|
#2
nunawnu2011-11-20 10:25
我的想法是，构造一个多叉树，每个结点表示一个城镇，有父亲节点和长子结点，以及哥哥、弟弟结点。
每个结点的直系孩子，表示这个和这个城镇直接相连的那些城镇，并且不包括父亲（虽然父亲结点的城镇也和本结点直接相连）。 然后就构造树，每次插入数据，都找当前的树上有没有要插入的数据，如果都没有，那就在将一个数据插入到根节点的直系孩子中，另一个结点作为这个结点的孩子插入。 如果仅有一个存在于树上，那就将另一个结点插入这个结点的直接孩子，作为长子。 如果两个孩子都在树上，那么肯定是根节点的不同的子树上，合并这两个树。 输入完成，就构造完成了这个树。 然后找最远点，然后用最远点找与它距离最远的点。输出距离。 请问这个题这么设计算法可以吗？如果可以，要怎么改进？ 网上测试的时候总是有一个点超时。  |
数据结构课程老师布置的作业……昨天已经截止……于是今天拿来问问大家……
【题目描述】
Shrek 在他生活的大沼泽里做小本生意。他每天骑着小驴Donkey 到大沼泽里的n 个小岛去卖货。
这n 个小岛由n‐1 座长度相等的桥相连，而且各岛之间都因此相互通达。
Shrek 每天早上从家出发，而且在路上不走回头路，也就是说同一天内他不可能经过同一岛或同
一桥两次或更多。到达某一岛后，他先卖一会儿货，然后随机选择并前往一个当天尚未去过的岛；如
果己无路可走，他就干脆停下来休息以打发掉当日剩余的时光，然后于次日再从该岛出发继续卖货。
问题是Donkey 的胃口太大。每经过一座桥，它都要吃掉一整包（体积为1 个单位）的草料。为
此，Shrek 要准备一个足够大的背包来装草料。当然，他特别想知道，究竟需要准备多大的背包，才
能保证自己永远不会因为这头馋嘴巴的懒驴，而在明明还有路可走的情况下却不得不停下来。
现在，请你通过编程帮助Shrek 算算，他到底需要一个多大的背包。
【输入】
第一行是正整数n，表示岛的总数，各岛从1 到n 编号。
接下来的n‐1 行各有以空格分隔的两个整数，表示由一座桥联通的两个岛（的编号）。
【输出】
仅有一行，含一个整数，即Shrek 所需背包的最小体积。
