洛谷P1268 树的重量

- 85通过
- 141提交
题目提供者该用户不存在
标签树形结构
难度提高+/省选-

提交该题讨论题解记录

题目描述

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

令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-l行，给出的是矩阵M的一个上三角(不包含对角线)，矩阵中所有元素是不超过100的非负整数。输入数据保证合法。

输入数据以n=0结尾。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

15
71

分析：这种求一大堆数相加的题目显然不好直接下手,遇到这类问题先把数据化小，先假设n=1,直接输出0即可......如果n=2,两个点分别为a,b,那么答案就是a,b的距离,如果有3个点呢？假设这个点为c,因为所有的点都是叶子节点，那么c一定是在a,b的路径上的分叉的路径上:(画的丑轻喷......),设d(i,j)为i到j的距离,那么答案就是(d(a,c) + d(b,c) - d(a,b)) / 2 + d(a,b)，如果多余3个节点呢？这个时候就必须要做一点特殊处理，把a当作一个“根”节点，因为所有的点都是连通的，那么j一定可以通过一条路径连接到a-i的路径上，那么再加一个点D,,可以发现答案其实就是3条线的和,但是我们只知道任意两个点之间的距离，怎么计算线呢？其实可以利用n=3的算法，答案为(d(a,c) + d(b,c) - d(a,b)) / 2 + d(a,b) + (d(a,d) + d(c,d) - d(a,c)) / 2这个时候要特别注意D是从哪条路径上分叉的，如果是从AB上分叉的可以发现会多算条路径(红色部分)怎么样才能不多算呢？其实可以发现，如果多加一个点，那么就要多计算一条路径，而这条路径就是最近的一条边分叉出来的，那么枚举边，计算最小值即可，同时要把A当作“根”节点，便于计算距离.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 55,inf = 1e18;

int n,d[maxn][maxn],ans,temp;

int main()
{
    while (scanf("%d", &n) && n)
    {
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
            {
                scanf("%d", &d[i][j]);
                d[j][i] = d[i][j];
            }
        ans = d[1][2];
        for (int i = 3; i <= n; i++)
        {
            temp = inf;
            for (int j = 2; j < i; j++)
                temp = min(temp, (d[1][i] + d[j][i] - d[1][j]) / 2);
            ans += temp;
        }
        printf("%d
", ans);
    }

    return 0;
}