问题4025--构造完全图4025: 构造完全图
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
对于完全图 G，若有且仅有一棵最小生成树为 T，则称完全图 G 是树 T 扩展出的。
给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。
输入
第一行 N表示树 T 的点数；
接下来 N-1 行三个整数 Si,Ti,Di；描述一条边（Si,Ti）权值为 Di；
保证输入数据构成一棵树。
输出
输出仅一个数，表示最小的完全图 G 的边权和。
样例输入
4
1 2 1
1 3 1
1 4 2
样例输出
12
样例解释
添加 D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。
来源/分类
[提交] [状态]