[Luogu P1268] 树的重量
洛谷传送门
题目描述
树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树,其叶节点表示一个物种,两个叶节点之间的距离表示两个物种的差异。现在,一个重要的问题是,根据物种之间的距离,重构相应的“进化树”。
令,用一个上的矩阵来定义树。其中,矩阵满足:对于任意的,,,有。树满足:
1.叶节点属于集合;
2.边权均为非负整数;
3.,其中表示树上i到j的最短路径长度。
如下图,矩阵描述了一棵树。
树的重量是指树上所有边权之和。对于任意给出的合法矩阵,它所能表示树的重量是惟一确定的,不可能找到两棵不同重量的树,它们都符合矩阵。你的任务就是,根据给出的矩阵,计算所表示树的重量。下图是上面给出的矩阵所能表示的一棵树,这棵树的总重量为。
输入输出格式
输入格式:
输入数据包含若干组数据。每组数据的第一行是一个整数。其后行,给出的是矩阵的一个上三角(不包含对角线),矩阵中所有元素是不超过的非负整数。输入数据保证合法。
输入数据以结尾。
输出格式:
对于每组输入,输出一行,一个整数,表示树的重量。
输入输出样例
输入样例#1:
5
5 9 12 8
8 11 7
5 1
4
4
15 36 60
31 55
36
0
输出样例#1:
15
71
解题分析
两个点的时候显然就是两点距离, 我们从三个点开始讨论。
如果我们原来钦定了两个点, 那么现在多出来的这条链的长度就是。
那么四个点的情况呢?
很明显, 如果这个新点是从我们选择的两个钦定的点路径上“生长”出去的, 计算出的值就最小, 因此我们每次选取这个值最小的加入到贡献中即可。
代码如下:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <climits>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 105
int dis[MX][MX];
int dot, ans;
int main(void)
{
int mn;
W (233)
{
scanf("%d", &dot); if(!dot) break;
for (R int i = 1; i <= dot; ++i)
for (R int j = i + 1; j <= dot; ++j)
scanf("%d", &dis[i][j]), dis[j][i] = dis[i][j];
ans = dis[1][2];
for (R int i = 3; i <= dot; ++i)
{
mn = INT_MAX;
for (R int j = 2; j < i; ++j) mn = std::min(mn, (dis[1][i] + dis[i][j] - dis[1][j]) / 2);
ans += mn;
}
printf("%d\n", ans);
}
}