最新消息:680元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 【例 4】次小生成树

C++ 少儿编程 1026浏览 0评论

友情提示:680元/半年,儿童学编程,就上码丁实验室

【题目描述】

原题来自:BeiJing 2010 组队赛

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

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

【输入】

第一行包含两个整数 $N$ 和 $M$,表示无向图的点数与边数;

接下来 MM 行,每行三个数 $x,y ,z$,表示点 $x$ 和点 $y$ 之间有一条边,边的权值为 $z$。

【输出】

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

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

【输入样例】

5 6 
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6

【输出样例】

11

【提示】

数据范围与提示:

对于全部数据,$1≤N≤10^5 ,1≤M≤3×10^5$ ,数据中无向图无自环,边权值非负且不超过 $10^9$ 。

您必须 登录 才能发表评论!