编程介的小学生 2017-10-27 13:39 采纳率: 20.5%
浏览 822
已采纳

Tree Size Problem

Description

Trees are used to represent the evolutionary relationship of species. An evolutionary tree is a edge-weighted tree with each leaf representing one species. The distance between two leaves on the tree represents the dissimilarity of these two species. An important issue in computational biology is to construct the evolutionary tree from the observed dissimilarities.
Let N = {1..n}. An n*n matrix M is a metric over N if it is symmetric, nonnegative, and M[i, j] + M[j, k] >= M[i, k] for any 1<= i, j, k <=n (i.e., triangle inequality). A metric is a tree metric if it can be realized by a tree, i.e., there exists an edge-weighted tree T such that
1. the leaf set is N;
2. the weight of each edge is nonnegative;
3. and d(T, i, j) = M[i, j] for any i, j <= N, where d(T, i, j) is the shortest path length between i and j on the tree T.
For example, the following matrix is a tree metric. The corresponding tree is given in Figure 8.


The size of a tree is defined to be the total weight of the tree edges. For a tree metric, it has been shown that the tree size is unique, i.e., it is impossible to find two trees of different sizes realizing the same tree metric. Your task is to design a program to compute the tree sizes of the given tree metrics. The following simple example may be helpful. For the case of only two species, the tree has only one edge and the tree size is just the distance between the two species. Let us consider the case of three species a, b, and c. Let T be the corresponding tree. Since T has three leaves, there is an internal node x. By definition, the path length d(T, a, b) = M[a, b]. Since x is a vertex on the path between a and b, all we need to do is to determine the weight (length) of edge (x, c). Let w(x, c) denote the weight of edge (x, c). We have
w(x, c) + w(x, a) = M[a, c],
w(x, c) + w(x, b) = M[b, c],
and w(x, a) + w(x, b) = M[a, b].
Therefore, w(x, c) = (M[a, c] +M[b, c] -M[a, b])/2.
Input

The input file consists of several test cases. The first line of each test case is a positive integer n, 2 < n < 30. The following n - 1 lines represent the upper triangle of the tree metric, but the diagonal is not included. Each line is for one row, and elements are separated by spaces. All the elements are nonnegative integers less than 100. The last case is followed by a "0" to indicate the end of input. You may assume that the test data are all tree metrics, and it is not necessary to check them.
Furthermore, the size of a tree is the sum of all integers in the test case except the integers in the first line of the test case.
Output

For each test case, output the tree size in one line.
Sample Input

5
5 9 12 8
8 11 7
5 1
4
4
15 36 60
31 55
36
0
Sample Output

15
71

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-11-13 14:37
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能