C++题目不懂，帮帮忙

显示全部楼层 · 2010-7-5 16:27:26

猫猫把嘴伸进池子里，正准备“吸”鱼吃，却听到门铃响了。猫猫擦了擦脸上的水，打开门一看，那人正是她的好朋友——川川。
川川手里拿着一辆玩具汽车，对猫猫说：“这是我的新汽车！”接着，伴随一阵塑料叩击声，玩具汽车的车门竟开了，一只蜗牛慢慢吞吞爬了出来。
“哇！这么大的蜗牛……”猫猫惊讶道。
“这是我的宠物蜗牛，他叫点点。”川川介绍道。
“把他送给我好吗？”猫猫央求道。
“可以让他陪你几天，但是不能送给你……”
点点沿着川川的身体，爬到了地上，又移到了猫猫的池子旁边，只听见猫猫向川川介绍她的“创意吃鱼法”，心里不禁起了一丝凉意：“这个女生太毒了……吃鱼前还要玩鱼……”转眼一看，池中的鱼依旧畅快地游来游去。
“或许这些鱼听不懂猫语吧……好在我会一点儿猫语，也会一点鱼语……阿弥陀佛，善哉善哉。我还是救救这些鱼吧……”点点自言自语，一边费力地移动着身躯。他认识到——单凭自己的力量，把猫猫的阴谋告诉每一条鱼，似乎不太可能——自己底盘太低，走不快，看来只得想其他办法来传达信息。一翻认真思考之后，点点想到，如果把猫猫的计划告诉其中一条鱼，再让鱼们互相传达消息，那么在相对较短的时间内，每条鱼都会得知猫猫的计划。
鱼们的社会等级森严，除了国王菜鱼之外，每条鱼均有且只有一个直接上级，菜鱼则没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。
绝对不会出现这样两条鱼A、B：A是B的上级，B也是A的上级。
最开始的时刻是0，点点要做的，就只是用1单位的时间把猫猫的阴谋告诉某一条“信息源鱼”，让鱼们自行散布消息。在任意一个时间单位中，任何一条已经接到通知的鱼，都可以把消息告诉他的一个直接上级或者直接下属。
现在，点点想知道：
1.到底需要多长时间，消息才能传遍池子里的鱼？
2.使消息传递过程消耗的时间最短，可供选择的“信息源鱼”有那些？
输入数据：
有多组输入数据，每组数据：
第一行有一个数N（N≤1000），表示池中的鱼数，池鱼按照1到n编上了号码，国王菜鱼的标号是1。
第2行到第N行（共N-1行），每一行一个数，第I行的数表示鱼I的直接上级的标号。
输出数据：
对于每组输入数据：
第一行有一个数，表示最后一条鱼接到通知的最早时间。

输入样例：
8
1
1
3
4
4
4
3
输出样例：
5
谢谢
我要过程。。写出来的

千问 · 2010-7-5 16:27:26

这个可以用图来做！求得每个结点到其他的结点的最短路的最大值（单个结点到其他结点最短路会有n-1个，也就是在这n-1个中取个最大值），这样你会得到n个最大值，而这n个最大中的最小值便是你要求的最后一条鱼收到通知的最早时间！方法和你说了，自己试着去做呗！难道你不想提高啊！这分我不要了！

千问 · 2010-7-5 16:27:26

这是一道排列组合，再求极值题。我上次给人家做过类似的题，但是做完后，找不到出题人，白做了。希望百度能解决这个问题。

千问 · 2010-7-5 16:27:26

不是吧，这么强大的题目像看小说一样！！！