【次小生成树】

题目描述

小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说: 如果最小生成树选择的边集是 EM,严格次小生成树选择的边集是 ES,那么需要满足:

其中 value(e) 表示边 e 的权值。

这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。

输入格式

第一行包含两个整数 N 和 M ,表示无向图的点数与边数。
接下来 M 行,每行 3 个数 x y z 表示,点 x 和点 y 之间有一条边,边的权值为 z 。

输出格式

包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

样例数据 1

输入

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

输出

11

备注

【数据范围】
数据中无向图无自环;
50% 的数据:N≤2000 M≤3000;
80% 的数据:N≤50000 M≤100000;
100% 的数据:N≤100000;M≤300000,
边权值非负且不超过 109 。

次小生成树模板题,先求最小生成树,再枚举点点间权值最大的那条边然后替换为没在树中的点,这样一定是次小生成树,不过本题要求严格的次小生成树,所以若添加的边和原最大边一样就不能添加(添加了是等效的),所以还要记录个蛋疼的次大边,然后最大边不行就替换次大边,找两点间权值最大的边用倍增法,其实就是求LCA然后从LCA往两边找……。话说求LCA用DFS有一个点要爆栈TAT必须BFS

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*