网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
小树
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | treec.in | 输出文件 | treec.out |
【题目描述】
这有一棵带根的树有 N 个节点标号从 0 到 N-1。根标号为 0。每条边连接两个节点,并且有权重。你的工作是找到 $S$,一个顶点集合$\{s_1,s_2,\cdots,s_m\} (0\le m < N)$,满足以下条件:
(1)根不在 $S$ 中,这就意味着:$0<s_i<N (1\le i \le m)$;
(2)$s_i$ 和 $s_j$ 只有一个公共祖先,这就意味着:除根外他们没有公共祖先。
(3)这里有两个联系在 $W=\{w_1,w_2,\cdots,w_m\} $ 和 $D=\{d_1,d_2,\cdots,d_m\}$ ,$w_i$ 是从根到 $s_i$ 的路径权重总和。$d_i$ 是从根到 $s_i$ 的边数总和。这个 $ S = \sum w_i / \sum d_i (1\le i \le m) $ 的平均结果是最大的。
【输入格式】
输入第一行有一个整数 T 表示测试数据个数。每组数据以整数 n 开始 (1≤n≤1000),树的节点个数。下面 N-1 行每行包括 3 个整数 i, j, k ,表示这是一个有向边从 i 到 j 权重为 k。
【输出格式】
每组数据输出一个实数,S 的最大平均数。
【样例输入】
3 1 2 0 1 2 3 0 1 1 0 2 2
【样例输出】
0.00 2.00 2.00
【评测方式】
评测插件判断该答案与标准答案差距不超过 0.01 即可算做正确。每答对一个询问得到 1/T 的分数。