HBC236594[ZJOI2007]棋盘制作,动态规划差分构造题解（最小生成树的权重定义）

凉芷算法基础篇 2023-11-09 23:59:02 69 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

小宝获得了一个可重集合，集合中有nnn个整数，现在小宝想要利用这nnn个数构造一颗最小生成树，这里的最小生成树的权重定义为每条树上边权值的和，每条树上边的权值为其所连接两个整数的差的绝对值，显然这样的最小生成树可能不止一颗，所以你还需要输出所有最小生成树中最长树链最短的那一颗的最长树链长度，这里的树链长度指的是树链中结点的个数，与边权和点权无关，

小宝获得了一个可重集合，集合中有 nnn 个整数，现在小宝想要利用这 nnn 个数构造一颗最小生成树。这里的最小生成树的权重定义为每条树上边权值的和，每条树上边的权值为其所连接两个整数的差的绝对值。显然这样的最小生成树可能不止一颗，所以你还需要输出所有最小生成树中最长树链最短的那一颗的最长树链长度。这里的树链长度指的是树链中结点的个数，与边权和点权无关。在本题中，你需要输出最小生成树的权值，以及所有最小生成树中最长树链的最短长度。