「HLOI2016」农场修路

题目描述

小明是一个快乐的农场主，他有 N 个农场，编号从 1 到 N，因为每个农场距离很远，现在他想修一些路使得任意两个农场都有道路能够到达。设计师给出了 N 个农场由 M 条公路相连的设计图，小明希望修的道路尽可能的少并且在修完的所有道路中最长的路程和最短的路程之间差值最小。

输入

第一行给出 N, M；

接下来 M 行，每一行包含三个整数：u, v, c，表示农场 u 和农场 v 之间有一条路可以互达，路程 c；

保证无重边，无自环。

输出

输出一行包括一个整数，表示在修完的所有道路中最长的路程和最短的路程之间的最小差值。如果不能实现任意两个农场都有道路能够互达，输出  − 1。

样例输入

3 3
1 2 1
1 3 2
2 3 3

样例输出

1

数据范围及约定

对于 30% 的数据有 2 ≤ N ≤ 20；

对于 60% 的数据有 2 ≤ N ≤ 50；

对于 100% 的数据有 。

时间限制与空间限制

时间限制：5000ms，空间限制：128MB。

题解

黑历史题，详见 UVa1395 Slim Span。

因为当最小边确定时，最小生成树唯一确定，所以枚举所有最小边，生成最小生成树，然后比较答案，选择最优解。

时间复杂度： 𝒪(mlogm+mn)，空间复杂度：𝒪(m)。

我也不知道为什么要开五秒。

代码见这里。