PID366 / 宿命的P.S.S
题目描述

1.背景描述Background

P.S.S:“我来自哪里?”

WH:“你来自一个图。”

P.S.S:“我是谁?”

WH:“你是最小生成树。”

P.S.S:“我又要到哪里去?”

WH:“你要成为一个最小完全图(边权之和最小的完全图)。”

P.S.S:“为……为什么啊?”

WH:“这是你的宿命!因为你无聊!!!P.S.S!”

2.问题描述Description

最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因,把这件事交给了你。

PS: 可以保证,这个最小生成树对于最后求出的完全图是唯一的。

7.时间限制Time Limitation

每个测试点1s。

8.数据规模:

Test1-Test10 n<60

Test11-Test25 n<20000

注释Hint:

对于样例1,我们只需在1-3间加入一条边权为8的边即可得到最小完全图。其权和是4+7+8=19。对于样例2,我们在2-3间加入一条边权为2的边,在2-4和3-4间加入边权为3的边即可得到最小完全图,其权和是:1+1+2+2+3+3=12。

感谢吴豪牛对比赛的支持!!!

输入格式

输入的第一行是一个整数n,表示生成树的节点数。

接下来有n-1行,每行有三个正整数,依次表示每条边的端点编号和边权。

(顶点的边号在1-n之间,边权<maxint)

输出格式

一个整数ans,表示以该树为最小生成树的最小完全图的边权之和。

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