编程介的小学生 2018-12-08 16:26 采纳率: 20.5%
浏览 407
已采纳

这个小问题,用算法解决的思路是什么,c语言

Problem Description
Mike has just found a dungeon. Inside there are n rooms and p treasure chests. Chests 1,...,p are located in room v1,...,vp respectively. The rooms are connected by n−1 passages. Any two rooms connected by a passage are considered adjacent. This dungeon is very special that there exists a path between any two rooms. Among these treasure chests, only chest 1 can be taken in the very beginning, others must be taken in order. That is, only after chest i is taken, may chest i+1 be taken as well, for every i∈{1,...,p−1}.

Mike is lazy, so he dislikes to explore the dungeon on his own feet. Therefore, Mike sends his robot dog, Blot, to collect the treasures in the dungeon. Blot can automatically collect the treasures from the chests, and it takes Blot exactly a second to move to any adjacent room. However, Blot’s movement is uncontrollable. Blot moves to all adjacent rooms with the same probability. For example, if there are k adjacent rooms, then Blot will move to any of them with probability 1k. Please help mike to compute the expected time that Blot collects all p treasures for him.

Input
The first line on the input contains an integer T(T≤10). There will be T test cases. The first line of each test case contains an integer n(2≤n≤50000) indicating the number of rooms in the dungeon. The rooms are numbered from 0 to n−1. Each of the following n−1 lines contains two integers u and v(u,v∈{0,...,n−1}) indicating room u and room v are adjacent.

The next line contains an integer q(q≤100) indicating the number of scenarios. Each of the following q lines represents a scenario which consists of some integers p,v0,v1,...,vp separated by blanks. The first integer p(0<p≤500) indicates there will be p treasure chests. The second integer v0 indicates that Blot is in room v0 at the beginning. For i∈{1,...,p}, the i−th treasure will be spawn at room vi. You may assume vi ≠ vi-1 for every i∈{1,...,p}.

Output
For each test case, output q lines, and the j−th of them corresponds to the j−th scenario of the test case. For each scenario, output the expected time in seconds such that Blot collects all treasures. Print the answer to the fourth decimal place, and separate two consecutive test cases with a blank line.

Sample Input
2
3
1 0
1 2
2
1 0 1
2 0 2 1
4
0 1
2 0
3 0
1
3 0 1 0 1

Sample Output
1.0000
5.0000

11.0000

  • 写回答

1条回答

  • threenewbee 2019-03-29 00:21
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名