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 iij jjk 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满足叶节点属于集合N NN边权均为非负整数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\ (2n30)n(2n30)。其后n − 1 n-1n−1行给出的是矩阵M MM的一个上三角不包含对角线矩阵中所有元素是不超过100 100100的非负整数。输入数据保证合法。输出格式对于每组输入输出一行一个整数表示树的重量。输入输出样例 #1输入 #15 5 9 12 8 8 11 7 5 1 4输出 #115输入输出样例 #2输入 #24 15 36 60 31 55 36输出 #271解题思路本题是树形结构的贪心构造问题。给定一个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 11和2 22它们之间的边权就是M [ 1 ] [ 2 ] M[1][2]M[1][2]树的重量初始为M [ 1 ] [ 2 ] M[1][2]M[1][2]。依次将节点3 , 4 , … , n 3,4,\dots,n3,4,…,n加入树中。每加入一个节点i ii需要确定它应该连接到已有树中的哪条边上以及连接边的长度。为了使树的重量最小即插入的边权最小需要枚举所有可能的插入位置。关键观察当新节点i ii加入时它必然连接到已有树中的某条边上的某个点可能是非叶节点。设该连接点为p pp则i ii到p pp的距离d dd就是新增的边权。对于任意两个已有的叶节点j jj和k kk1 ≤ j k i 1 \le j k i1≤jki如果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]2dM[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}d2M[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 0n0则结束。将上三角矩阵读入并补全为对称矩阵dis[i][j]。基础情况若n ≥ 2 n \ge 2n≥2答案初始为ans dis[1][2]节点 1 和 2 之间的边。逐步插入节点对于i 3 i 3i3到n nn初始化一个极大值tmp用于记录插入节点i ii所需的最小边权。枚举所有可能的插入路径端点。由于固定一个端点为节点 1 即可保证正确性见题解证明只需令j 2 j 2j2到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_{i3}^{n} (i-1) O(n^2)∑i3n​(i−1)O(n2)。n 30 n 30n30运算量极小完全可行。空间复杂度需要存储n × n n \times nn×n的距离矩阵O ( n 2 ) O(n^2)O(n2)空间消耗可忽略。总结通过逐步向已有树中插入新节点并利用树的最短路径性质将新增边权的计算转化为两个已有叶节点到新节点的距离减去它们之间距离的一半。取所有可能组合的最小值作为最优插入边权累加即可得到树的最小总重量。该贪心策略的正确性由树的结构性质保证算法简单且高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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 i1;in;i)for(ll ji1;jn;j)scanf(%lld,dis[i][j]);ll ansdis[1][2];for(ll i3;in;i){ll tmp0x7fffffff;for(ll j2;ji;j)tmpmin(tmp,(dis[1][i]-dis[1][j]dis[j][i])/2);anstmp;}printf(%lld\n,ans);}return0;}