luogu1268树的重量|题解

luogu1268树的重量|题解

九月 15, 2018

本文引用洛谷图床图片可能无法显示,请复制链接至新标签页查看

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

令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描述了一棵树。

img

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

img

非常巧妙的一道构造题.


题面指出 $对于任意的i,j,k 有M[i,j] + M[j,k] \geq M[i,k]$

那么很显然$M$描述的是两点之间的最短路了,也就是$M[i,j]=M[i,lca(i,j)]+M[j,lca(i,j)]$


我们取出一个叶子节点$a$,将它作为树根.

接下来我们逐个将叶子加入这颗树里.这个叶子一定会产生一个新枝,我们把这个叶子产生的枝加入答案$ans$

对于第二个叶子$b$,显然它只能直接和$a$连一条边,$ans=M[a,b]$

对于第三个叶子$c$,显然它只能加入链$[a,b]$中,根据$M$的信息我们可以算出$c$产生的枝长度$L$为$(M[a,c]+M[b,c]-M[a,b])/2$,将这个数字加入$ans$

对于第四个叶子$d$,事情就没有这么简单了.它有可能加入链$[a,b]$,分枝长度$L_1$;也有可能加入链$[a,c]$,分枝长度$L_2$.我们分类讨论不同情况:

  1. 分支点位于$[a,lca(b,c)]$,则$L_1=L_2$
  2. 分支点位于$[lca(b,c),b]$,则$L_1$为$d$到$lca(b,d)$的距离;$L_2$为$d$到$lca(c,d)即lca(b,c)$的距离.显然$L_1<L_2$.如果我们认为$L$为$L_2$,那么$lca(b,d)到lca(b,c)$的这一段距离就会重复计算(我们在加入$b$的时候就把这一段加入$ans$了).所以$L$为$L_1$
  3. 分支点位于$[lca(b,c),c]$的时候情形同上

综上,对于第四个节点,$L=\min(L_1,L_2)$

……

推广到第$n$个节点,$L=\min{L_i}$

img

img

图片引自TsReaper的博客


代码如下

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#define LL int
using namespace std;
LL map_[100][100],len[100],n;
int main(){
        while (1){
                scanf("%d",&n);
                if (n == 0)
                        break;
                else {
                        memset(map_,0,sizeof(map_));
                        memset(len,0x3f,sizeof(len));
                        for (LL i = 1;i <= n;++ i){
                                for (LL j = 1 + i;j <= n;++ j){
                                        scanf("%d",&map_[i][j]);
                                        map_[j][i] = map_[i][j];
                                }
                        }
                }
                LL ans = len[2] = map_[1][2];
                for (LL i = 3;i <= n;++ i){
                        for (LL j = 2;j < i;++ j){
                                len[i] = min(len[i],(map_[i][j] + map_[i][1] - map_[1][j]) >> 1);
                        }
                        ans += len[i];
                }
                printf("%d\n",ans);
        }

        return 0;
}

文结