PID333 / 发明测试数据
题目描述

题目背景

出题目是一件很费力的事,为一道题出数据则是更加令人痛苦的事情。Wish 现在正在帮一些学弟学妹们出一些信息学竞赛的基础题,但在出数据的过程中遇到了一些棘手的问题……

Wish 出的题目是:找出给定带权图图的最小生成树,为了加大一点难度,给定的图均为无向完全图(即任意两个点均连一条边),并且 Wish 希望这个图中各边的权值尽可能大。

Wish 制作测试数据的方法比较特别,他是先生成一个树,然后再向这个树中加边来构造完全图。但是他发现他的程序有些问题,有的时候最后生成的图的最小生成树并不是开始给定的那个。

由于已经生成了很多组数据,为了检测出哪些数据有问题,他想让你计算出给定的树可构造出的完全图的最小边权值和是多少,于是生成的小于这个和的图的数据就可以筛去了。

题目描述

给定一个树 T,找出一个无向完全图 G,使得 T 是 G 的最小生成树,并且 G 各边的权值之和尽可能小,输出这个最小权值和即可。

输入格式

每个测试点包含多组数据,第一行一个数 t,表示共 t 组测试数据。

后接 t 组测试数据。

每组数据之前有一个空行。

每组数据的第一行有一个数 n,表示给定树的节点数(节点编号 1-n)。

之后 n-1 行,每行三个数 ai、bi、wi,表示节点 ai 和 bi 之间连有一条边,其权值为 wi。

数据范围

1 <= t <= 20

1 <= n <= 15000

1 <= ai, bi <= n

1 <= wi <= 10000

输出格式

对于每组测试数据,输出一行,表示求出的最小权值和。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论