[省选] [最小生成树] HLOI2016Day2 农场修路

问题描述 Description

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

输入 Input

第一行给出N,M$N,M$。 接下来M$M$行，每一行包含三个整数：u,v,c$u,v,c$,表示农场u$u$和农场v$v$之间有一条路可以互达，路程c$c$。 保证无重边，无自环，0<c≤107$0/lt c/le 10^7$。

输出 Output

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

样例输入 Sample Input

3 3 1 2 1 1 3 2 2 3 3

样例输出 Sample Output

1

限制 Limits

对于30%$30/%$的数据有2≤N≤20$2/le N/le 20$ 对于60%$60/%$的数据有2≤N≤50$2/le N/le 50$ 对于100%$100/%$的数据有2≤N≤100,0≤M≤N×(N−1)2$2/le N/le 100,0/le M/le /frac{N/times (N-1)}{2}$

黑历史题，详见UVa1395 苗条的生成树。 因为当最小边确定时，最小生成树唯一确定，所以枚举所有最小边，生成最小生成树，然后比较答案，选择最优解。 时间O(mlogm+mn)$O(mlogm+mn)$ 我也不知道为什么要开5s$5s$。 Code