P1268 树的重量

    • 671通过
    • 1.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 构造 枚举,暴力 树形结构
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树,其叶节点表示一个物种,两个叶节点之间的距离表示两个物种的差异。现在,一个重要的问题是,根据物种之间的距离,重构相应的“进化树”。

    令N={1..n},用一个N上的矩阵M来定义树T。其中,矩阵M满足:对于任意的i,j,k,有M[i,j] + M[j,k] >= M[i,k]。树T满足:

    1.叶节点属于集合N;

    2.边权均为非负整数;

    3.dT(i,j)=M[i,j],其中dT(i,j)表示树上i到j的最短路径长度。

    如下图,矩阵M描述了一棵树。

    树的重量是指树上所有边权之和。对于任意给出的合法矩阵M,它所能表示树的重量是惟一确定的,不可能找到两棵不同重量的树,它们都符合矩阵M。你的任务就是,根据给出的矩阵M,计算M所表示树的重量。下图是上面给出的矩阵M所能表示的一棵树,这棵树的总重量为15。

    输入输出格式

    输入格式:

    输入数据包含若干组数据。每组数据的第一行是一个整数n(2<n<30)。其后n-1行,给出的是矩阵M的一个上三角(不包含对角线),矩阵中所有元素是不超过100的非负整数。输入数据保证合法。

    输入数据以n=0结尾。

    输出格式:

    对于每组输入,输出一行,一个整数,表示树的重量。

    输入输出样例

    输入样例#1: 复制
    5
    5 9 12 8
    8 11 7
    5 1
    4
    4
    15 36 60
    31 55
    36
    0
    
    输出样例#1: 复制
    15
    71
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。