Dark`Kris

Private blog

I'm spark , hope you fire


Luogu P1072 树的重量 解题报告

时隔近两年,我又重新回来写解题报告了,这题实在有趣(其实感觉构造这一类题都很有趣)。

题目描述

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

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

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

输入输出格式

输入格式:

输入数据包含若干组数据。每组数据的第一行是一个整数n(2<n<30)。其后n-1行,给出的是矩阵M的一个上三角(不包含对角线),矩阵中所有元素是不超过100的非负整数。输入数据保证合法。

输入数据以n=0结尾。

输出格式:

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

输入输出样例

输入样例#1:

5 5 9 12 8 8 11 7 5 1 4 4 15 36 60 31 55 36 0

输出样例#1:

15 71


解题思路

感谢TsReaper的解题思路与图片

这道题是一个图论相关的构造题,被归类在了洛谷试炼场-提高历练地-较复杂图论I里面,但我觉得实际上还是构造的成分比较多。

  • 当n=2时,显然答案为g[1][2]
  • 当n=3时,我们可以画出如下图:
    记蓝色线段为len,则有len=(g[1][3]+g[2][3]-g[1][2])/2
  • 当n=4时,我们可以画出如下图:

于是我们可以得出结论
其中

代码如下:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=35;
int g[maxn][maxn];
int len[maxn];
int n;
int main()
{
    while(scanf("%d",&n),n!=0)
    {
        memset(g,0,sizeof(g));
        for(int i=1;i<n;i++)
            for(int j=i+1;j<=n;j++)
            {
                scanf("%d",&g[i][j]);
                g[j][i]=g[i][j];
            }
        for(int i=3;i<=n;i++)len[i]=0xffffff;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<=i-1;j++)
                for(int k=j+1;k<=i-1;k++)
                {
                    len[i]=min(len[i],(g[j][i]+g[k][i]-g[j][k])/2);
                }
        }
        int ans=g[1][2];
        for(int i=3;i<=n;i++)
            ans+=len[i];
        printf("%d\n",ans);
    }
    return 0;
}

感谢阅读

Tips

Cancel

Thanks a lot,I will be better!

scan possible
scan possible
Scan and give tips as you wish

OpenAlipayScan it and give tips as you wish

Wait a minute,Loading