企业官网建设流程全解析

P1268 树的重量

网页链接

P1268 树的重量

题目描述

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

令N = { 1 , 2 , 3 , ⋯ , n } N=\{1,2,3,\cdots ,n\}N={1,2,3,⋯,n}，用一个N NN上的矩阵M MM来定义树T TT。其中，矩阵M MM满足：对于任意的i ii，j jj，k kk，有M [ i , j ] + M [ j , k ] ≥ M [ i , k ] M[i,j]+M[j,k] \ge M[i,k]M[i,j]+M[j,k]≥M[i,k]。树T TT满足：

1. 叶节点属于集合N NN；
2. 边权均为非负整数；
3. d T ( i , j ) = M [ i , j ] d_T(i,j)=M[i,j]dT​(i,j)=M[i,j]，其中d T ( i , j ) d_T(i,j)dT​(i,j)表示树上i ii到j jj的最短路径长度。

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

M = [ 0 5 9 12 8 5 0 8 11 7 9 8 0 5 1 12 11 5 0 4 8 7 1 4 0 ] M=\begin{bmatrix} 0 & 5 & 9 & 12 & 8 \\ 5 & 0 & 8 & 11 & 7 \\ 9 & 8 & 0 & 5 & 1 \\ 12 & 11 & 5 & 0 & 4 \\ 8 & 7 & 1 & 4 & 0 \\ \end{bmatrix}M=​059128​508117​98051​1211504​87140​​

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

输入格式

第一行是一个整数n ( 2 < n < 30 ) n\ (2<n<30)n(2<n<30)。

其后n − 1 n-1n−1行，给出的是矩阵M MM的一个上三角（不包含对角线），矩阵中所有元素是不超过100 100100的非负整数。输入数据保证合法。

输出格式

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

输入输出样例 #1

输入 #1

5 5 9 12 8 8 11 7 5 1 4

输出 #1

15

输入输出样例 #2

输入 #2

4 15 36 60 31 55 36

输出 #2

71

解题思路

本题是树形结构的贪心构造问题。给定一个n × n n \times nn×n的对称矩阵M MM，其中M [ i ] [ j ] M[i][j]M[i][j]表示树上叶节点i ii与j jj之间的最短路径长度。要求还原出这棵“进化树”并计算所有边权之和。题目保证矩阵合法，且树的重量唯一确定。

1. 问题等价转化

• 进化树是一棵带权无向树，叶节点对应集合N = { 1 , 2 , … , n } N = \{1,2,\dots,n\}N={1,2,…,n}，边权非负。
• 矩阵M MM给出了任意两个叶节点之间的最短距离。根据树的性质，任意两点间的最短路径是唯一的。
• 我们可以将问题转化为逐步向已有的树中插入新节点的过程：
  1. 最初只有节点1 11和2 22，它们之间的边权就是M [ 1 ] [ 2 ] M[1][2]M[1][2]，树的重量初始为M [ 1 ] [ 2 ] M[1][2]M[1][2]。
  2. 依次将节点3 , 4 , … , n 3,4,\dots,n3,4,…,n加入树中。每加入一个节点i ii，需要确定它应该连接到已有树中的哪条边上，以及连接边的长度。
  3. 为了使树的重量最小（即插入的边权最小），需要枚举所有可能的插入位置。
• 关键观察：当新节点i ii加入时，它必然连接到已有树中的某条边上的某个点（可能是非叶节点）。设该连接点为p pp，则i ii到p pp的距离d dd就是新增的边权。
• 对于任意两个已有的叶节点j jj和k kk（1 ≤ j < k < i 1 \le j < k < i1≤j<k<i），如果i ii连接到j jj与k kk的路径上的某点，那么根据树的最短路径性质，有：
  M [ j ] [ i ] = M [ j ] [ p ] + d , M [ k ] [ i ] = M [ k ] [ p ] + d M[j][i] = M[j][p] + d,\quad M[k][i] = M[k][p] + dM[j][i]=M[j][p]+d,M[k][i]=M[k][p]+d
  且p pp在j jj到k kk的路径上，所以M [ j ] [ p ] + M [ p ] [ k ] = M [ j ] [ k ] M[j][p] + M[p][k] = M[j][k]M[j][p]+M[p][k]=M[j][k]。
  由此可推出：
  2 d = M [ j ] [ i ] + M [ k ] [ i ] − M [ j ] [ k ] 2d = M[j][i] + M[k][i] - M[j][k]2d=M[j][i]+M[k][i]−M[j][k]
  即新增边权为：
  d = M [ j ] [ i ] + M [ k ] [ i ] − M [ j ] [ k ] 2 d = \frac{M[j][i] + M[k][i] - M[j][k]}{2}d=2M[j][i]+M[k][i]−M[j][k]​
• 由于j jj和k kk可以是已有树中任意两个叶节点，新节点i ii的最优插入位置对应的d dd应该是所有可能( j , k ) (j,k)(j,k)组合中的最小值。

2. 算法实现

• 初始化：读入n nn，若n = 0 n = 0n=0则结束。将上三角矩阵读入并补全为对称矩阵dis[i][j]。
• 基础情况：若n ≥ 2 n \ge 2n≥2，答案初始为ans = dis[1][2]（节点 1 和 2 之间的边）。
• 逐步插入节点：对于i = 3 i = 3i=3到n nn：
  • 初始化一个极大值tmp，用于记录插入节点i ii所需的最小边权。
  • 枚举所有可能的插入路径端点。由于固定一个端点为节点 1 即可保证正确性（见题解证明），只需令j = 2 j = 2j=2到i − 1 i-1i−1：
    • 计算候选边权：candidate = (dis[1][i] + dis[j][i] - dis[1][j]) / 2。
    • 更新tmp = min(tmp, candidate)。
  • 将tmp累加到答案ans中。
• 输出：输出最终的ans，即整棵树的总重量。

3. 复杂度分析

• 时间复杂度：对于每个新节点i ii（共n − 2 n-2n−2个），需要枚举j jj（最多i − 1 i-1i−1个），因此总运算量约为∑ i = 3 n ( i − 1 ) = O ( n 2 ) \sum_{i=3}^{n} (i-1) = O(n^2)∑i=3n​(i−1)=O(n2)。n < 30 n < 30n<30，运算量极小，完全可行。
• 空间复杂度：需要存储n × n n \times nn×n的距离矩阵，O ( n 2 ) O(n^2)O(n2)，空间消耗可忽略。

总结

通过逐步向已有树中插入新节点，并利用树的最短路径性质，将新增边权的计算转化为两个已有叶节点到新节点的距离减去它们之间距离的一半。取所有可能组合的最小值作为最优插入边权，累加即可得到树的最小总重量。该贪心策略的正确性由树的结构性质保证，算法简单且高效。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,dis[35][35];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);while(~scanf("%lld",&n)){if(!n)break;for(ll i=1;i<n;i++)for(ll j=i+1;j<=n;j++)scanf("%lld",&dis[i][j]);ll ans=dis[1][2];for(ll i=3;i<=n;i++){ll tmp=0x7fffffff;for(ll j=2;j<i;j++)tmp=min(tmp,(dis[1][i]-dis[1][j]+dis[j][i])/2);ans+=tmp;}printf("%lld\n",ans);}return0;}