Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits
Description
因为一场不小的地震，Y 省n 个城市之间的道路都损坏掉了，省长希望小X 将城市之间的道路重修一遍。
很多城市之间的地基都被地震破坏导致不能修路了，因此可供修建的道路只有m 条。因为施工队伍有限，省长要求用尽量少的道路将所有的城市连通起来，这样施工量就可以尽量少。不过，省长为了表示自己的公正无私，要求在满足上述条件的情况下，选择一种方案，使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小，即使这样的方案会使总价提升很多也没关系。
小X 现在手忙脚乱，希望你帮帮他。
Input
第一行包含两个整数n;m。
接下来m 行，每行包含三个整数a; b; c，表示城市a; b 之间可以修建一条价格为c 的无向道路。
Output
若存在合法方案，则第一行包含一个整数，表示最贵道路的价格和最便宜道路的价格的最小差值；
否则第一行包含一个整数−1。
Sample Input
输入1： 5 10 1 2 9384 1 3 887 1 4 2778 1 5 6916 2 3 7794 2 4 8336 2 5 5387 3 4 493 3 5 6650 4 5 1422 输入2： 2 0
Sample Output
输出1： 1686 输出2： -1
Data Constraint
• 对于30% 的数据，n;m ≤ 20。
• 对于60% 的数据，n ≤ 1000，m ≤ 4000。
• 对于100% 的数据，2 ≤ n ≤ 2000，0 ≤ m ≤ 15000，a ̸= b，1 ≤ c ≤ 2 × 10^9。
总结 ：
垃圾qsort
题解：
先排序， 确定左端点， 枚举右端点， 并查集维护。
时间复杂度有点大。卡一下并查集的常数k。
可以用深度标识dep[], 合并时小合到大的上面。
然后版本数组优化。 register， o3.
#include<bits/stdc++.h>
#define open(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout)
#define mem(a, b) memset(a, b, sizeof(a))
#define mcy(a, b) memcpy(a, b, sizeof(a))
#define pf printf
#define fo(i, a, b) for(register int i = a; i <= b; ++i)
#define N 2001
#define M 15001
#define inf 2147483647
using namespace std;
template<class T>
T in(T &x) {
x=0;
char ch = getchar(); int f = 0;
while(ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
while(ch >= '0' && ch <= '9') x = (x<<1) + (x<<3) + ch - '0', ch = getchar();
x = f ? -x : x;
return x;
}
int tag =0;
struct edge{
int u, v, d;
}E[M];
bool cmp(edge a, edge b) {
return a.d < b.d;
}
int n, m, ans, fa[N], dep[N];
int book[N], av;
int getfather(int x) {
if(book[x] < av) {
book[x] = av;
dep[x] = 0;
return fa[x] = x;
}
return fa[x] == x ? x : fa[x] = getfather(fa[x]);
}
void get_ans() {
fo(i, 1, m) { ++av;
// fo(j, 1, n) fa[j] = j, dep[j] = 0;
int st = E[i].d, cnt = 0;
fo(j, i, m) {
#define u E[j].u
#define v E[j].v
#define now E[j].d
if(now - st >= ans) break;
int fx = getfather(u), fy = getfather(v);
if(fx != fy) {
if(dep[fx] < dep[fy])fa[fx] = fy, ++dep[fy]; else fa[fy] = fx, ++dep[fx];
++cnt;
if(cnt == n - 1) {
ans = now - st;
tag = 1;
break;
}
}
#undef u
#undef v
#undef now
}
}
}
int main() {
open("road");
in(n), in(m);
fo(i, 1, m) in(E[i].u), in(E[i].v), in(E[i].d);
sort(E + 1, E + 1 + m, cmp);
ans = inf;
get_ans();
pf("%d\n", tag ? ans : -1);
return 0;
}
O（km ^ 2）