Skip to content

1254: 最小生成完全图

题目

题目描述

对于完全图 $G$ ,若有且仅有一棵最小生成树为 $T$,则称完全图 $G$ 是树 $T$ 扩展出的。

给你一棵树 $T$ ,找出 $T$ 能扩展出的边权和最小的完全图 $G$ 。

输入格式

第一行一个正整数 $N$,表示树 $T$ 的节点个数

接下来 $N - 1$ 行,每行三个用空格隔开的整数 $S_i, T_i, D_i$,描述了一条连接 $S_i, T_i$ 且权值为 $D_i$ 的边

保证输入是一棵树

输出格式

输出仅一个数,表示最小生成完全图 $G$ 的边权和

样例输入

text 4 1 2 1 1 3 1 1 4 2

样例输出

text 12

样例解释

添加三条边,$D(2,3)=2, D(3,4)=3, D(2,4)=3$ 即可

数据范围

时间限制:1000 ms 空间限制:512 mb

无捆绑测试

  1. $(\text{20 points})~ N \leq 10$
  2. $(\text{30 points})~ N \leq 10^3$
  3. $(\text{50 points})~ N\leq 10^5, 1\leq D_i \leq 10^5$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!