问题 2804 --次小生成树

2804: 次小生成树★★★★★

时间限制: 1 Sec  内存限制: 32767 MB
提交: 45  解决: 21
[提交][状态][命题人:]

题目描述

BeiJing 2010 组队赛

给定一张 N个点 M条边的无向图,求无向图的严格次小生成树。

设最小生成树的边权之和为sum ,严格次小生成树就是指边权之和大于 sum 的生成树中最小的一个。

输入

输出

包含一行,仅一个数,表示严格次小生成树的边权和。

数据保证必定存在严格次小生成树。

样例输入
Copy
5 6 
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6 
样例输出
Copy
11

提示

来源

 

[提交][状态]