|
|
|
|
背景 Background |
|
|
|
P.S.S:“我来自哪里？”
WH:“你来自一个图。”
P.S.S:“我是谁？”
WH:“你是最小生成树。”
P.S.S:“我又要到哪里去？”
WH:“你要成为一个最小完全图（边权之和最小的完全图）。”
P.S.S:“为……为什么啊？”
WH:“这是你的宿命！因为你无聊！！！P.S.S！”
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
最小生成树P.S.S在宿命的指引下找到了巫师Kismi。P.S.S希望Kismi能帮自己变成一个完全图。Kismi由于某些不可告人的原因，把这件事交给了你。
PS: 可以保证，这个最小生成树对于最后求出的完全图是唯一的。 |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
输入的第一行是一个整数n，表示生成树的节点数。
接下来有n-1行，每行有三个正整数，依次表示每条边的端点编号和边权。
（顶点的边号在1-n之间，边权<maxint）
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
一个整数ans，表示以该树为最小生成树的最小完全图的边权之和。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
每个测点1s |
|
|
|
|
|
|
|
来源 Source |
|
|
|
冰尘e溶化邀请赛第四题,吴豪原创题。
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1579 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
