题目分析

题意简述

树被用于表示物种间的进化关系，进化树是边带权的树，每个叶子节点代表一个物种，两叶子节点间的距离代表两物种的差异。给定一个 $n\times n$ 的矩阵 $M$，它是对称、非负且满足三角不等式的度量矩阵，若能找到一个边带权的树 $T$，使得叶子节点集合为 $\{1, 2, \cdots, n\}$，每条边权值非负，且树中任意两节点 $i$ 和 $j$ 的最短路径长度 $d(T, i, j)$ 等于 $M[i, j]$，则称 $M$ 为树度量矩阵。树的大小定义为树中所有边的权值之和，对于一个树度量矩阵，其对应的树的大小是唯一的。你的任务是计算给定树度量矩阵所对应的树的大小。

输入

• 输入包含多个测试用例。
• 每个测试用例的第一行是一个正整数 $n$（$2 < n < 30$）。
• 接下来的 $n - 1$ 行表示树度量矩阵的上三角部分（不包含对角线元素），每行元素用空格分隔，所有元素都是小于 $100$ 的非负整数。
• 最后一个测试用例后面跟着一个 $0$ 表示输入结束。

输出

对于每个测试用例，输出对应的树的大小，若结果为整数则直接输出，若结果小数部分小于 $0.4$ 则输出整数部分，否则输出整数部分加 $0.5$。

解题思路

数据读取

• 读取每个测试用例的 $n$ 值，若 $n$ 为 $0$ 则结束程序。
• 读取树度量矩阵的上三角部分，将其对称填充到整个矩阵 $dist$ 中，同时将对角线元素置为 $0$。

树大小计算

• 初始化一个布尔数组 $valid$ 用于标记节点是否有效，初始时所有节点都有效。
• 进行 $n - 1$ 次循环，每次循环尝试找到可以合并的节点对：
  • 遍历所有有效的节点对 $(a, b)$，对于每一对节点，再遍历其他有效节点 $c$，计算 $dist[a][c] - dist[b][c]$ 的值。若对于所有的 $c$ 该值都相同，则说明可以将节点 $b$ 合并到节点 $a$ 上。
  • 合并节点 $b$ 到节点 $a$ 时，将节点 $b$ 标记为无效，将 $dist[a][b]$ 累加到树的大小 $size$ 中。
  • 若 $dist[a][c] - dist[b][c]$ 的值不为阈值 $THRES$，则更新其他节点到节点 $a$ 的距离。

结果输出

• 将计算得到的树的大小 $size$ 转换为整数 $size\_$。
• 根据 $size - size\_$ 的值判断输出格式，若小于 $0.4$ 则输出整数部分，否则输出整数部分加 $0.5$。

代码实现

#include <iostream>
#include <stdio.h>
using namespace std;

int n;
double dist[33][33];
const double THRES = 1000000.0;

int main() {
    while(1){
        scanf("%d", &n);
        if(!n) return 0;
        for(int i = 1; i <= n; i++){
            dist[i][i] = 0;
            for(int j = i+1; j <= n; j++){
                int temp;
                scanf("%d", &temp);
                dist[i][j] = (double) temp;
                dist[j][i] = dist[i][j];
            }
        }
        double size = 0;
        bool valid[40];
        for(int i = 1; i <= n; i++) valid[i] = 1;
        for(int i = 1; i <= n-1; i++){

            for(int a = 1; a <= n; a++){
                if(!valid[a]) continue;
                for(int b = 1; b <= n; b++){
                    if(!valid[b] || b==a) continue;
                    double Dist = THRES;
                    bool ky = 1;
                    for(int c = 1; c <= n; c++){
                        if(!valid[c] || c==a || c==b) continue;
                        double tempDist = dist[a][c] - dist[b][c];
                        if(Dist != THRES && tempDist != Dist){
                            ky = 0;
                            break;
                        }
                        Dist = tempDist;
                    }
                    if(ky){
                        valid[b] = 0;
                        size += dist[a][b];
                        if(Dist != THRES){
                            double dt = (Dist + dist[a][b])/2;
                            for(int q = 1; q <= n; q++){
                                if(!valid[q] || q==a) continue;
                                dist[q][a] -= dt;
                                dist[a][q] -= dt;
                            }
                        }
                        goto onePhase;
                    }
                }
            }
            onePhase:
            continue;
        }
        int size_ = (int)size;
        if(size-size_<0.4) printf("%d\n", size_);
        else printf("%d.5\n", size_);
    }
    return 0;
}

代码说明

1. 全局变量：

   • n：表示物种的数量。
   • dist[33][33]：存储树度量矩阵。
   • THRES：一个很大的阈值，用于判断 $dist[a][c] - dist[b][c]$ 是否首次计算。

2. 输入处理：

   • 使用 while(1) 循环读取多个测试用例，当 $n$ 为 $0$ 时退出循环。
   • 对于每个测试用例，读取矩阵的上三角部分，并将其对称填充到整个矩阵中，同时将对角线元素置为 $0$。

3. 树大小计算：

   • valid 数组用于标记节点是否有效。
   • 通过三重循环遍历所有可能的节点对 $(a, b)$，并检查其他节点 $c$ 计算 $dist[a][c] - dist[b][c]$ 的值是否相同。
   • 若相同，则将节点 $b$ 合并到节点 $a$ 上，更新 $valid$ 数组和 $size$ 的值，并根据需要更新其他节点到节点 $a$ 的距离。

4. 结果输出：

   • 将 $size$ 转换为整数 $size\_$，根据 $size - size\_$ 的值判断输出格式。