M_sea

洛谷1268 树的重量
NOIP2018冲刺计划 Day1:树的重量(其实只是因为我太蒻了没拿到1=而已)题目描述树可以用来表示物种之间的...
扫描右侧二维码阅读全文
13
2017/11

洛谷1268 树的重量

NOIP2018冲刺计划 Day1:树的重量
(其实只是因为我太蒻了没拿到1=而已)

题目描述

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

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

1

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

2

传送门

算法

枚举+构造。

不难发现,M[i][j]表示的就是i到j的最短路径。

那么先建一颗1-2的树,然后把3-n依次加入。
对于第i个节点,枚举它之前的所有节点,使所有的非叶子节点尽可能地靠近叶子节点,远离根节点,使公共部分尽量多。

这话有点抽象,我们来具体看看。
画个图就能发现,把节点i设为1-j路径上分出来的点,则多出来的长度为(d[1][i]+d[j][i]-d[1][j])/2
这个应该很好理解。

那么每次找一个最小的加入就好了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int g[50][50];
int main() {
    int n;
    do {
        n=read(); if (n==0) break;
        for (re int i=1;i<=n;i++)
            for (re int j=i+1;j<=n;j++)
                g[i][j]=g[j][i]=read();
        int ans=g[1][2];
        for (re int i=3;i<=n;i++) {
            int now=2147483647;
            for (re int j=1;j<i;j++)
                now=min(now,(g[1][i]+g[i][j]-g[1][j])/2);
            ans+=now;
        }
        printf("%d\n",ans);
    } while (n!=0);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 29 PM

发表评论