2013
11-09

# Tree Size Problem

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.

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.

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

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


15
71


//* @author:
import java.util.*;
public class Main {

static int value[][]=new int[50][50];
static int ans,n;

static void calc()
{
int i, j, temp, k, s;
for( k=0; k< n-2; k++ )
{
s = 10000000;
for( i = k+1; i < n; i++ )
for( j = i+1; j < n; j++ )
{
if( (temp = (value[i][k]+value[j][k]-value[i][j])/2 ) < s )
s = temp;
}

for( i = k+1; i < n; i++ ){
value[i][k] -= s;
value[k][i] -= s;
}
ans += s;
}
ans += value[n-2][n-1];
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);
int i, j;

while( in.hasNext())
{
n=in.nextInt();

if( n == 0 ) break;
for( i=0; i< n; i++ )
{
for( j=i+1; j< n; j++ )
{
value[i][j]=in.nextInt();
value[j][i] = value[i][j];
}

value[i][i] = 0;
}
ans = 0;
calc();
System.out.printf( "%d\n",ans );
}
}
}

1. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

3. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了

4. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

5. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

6. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。