1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include <iostream>
#include <algorithm>
#define maxn 50010
#define maxm 200010
#define INF 1000000000
using namespace std;
int n, m;
struct Edge {
int u, v, w;
} e[maxm];
#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct LinkCutTree {
int v, val, ch[2];
bool rev;
} T[maxn + maxm]; int f[maxn + maxm];
void init_LCT() {
for (int i = 1; i <= m; ++i) T[i + n].val = i; e[0].w = INF;
}
inline int get(int i) {
if (T[f[i]].ch[0] == i) return 0;
if (T[f[i]].ch[1] == i) return 1;
return -1;
}
inline void maintain(int i) {
T[i].v = T[i].val;
if (e[T[lc].v].w < e[T[i].v].w) T[i].v = T[lc].v;
if (e[T[rc].v].w < e[T[i].v].w) T[i].v = T[rc].v;
}
inline void setr(int i) {
if (!i) return ;
T[i].rev ^= 1; swap(lc, rc);
}
inline void push(int i) {
bool &rev = T[i].rev;
if (rev) setr(lc), setr(rc);
rev = 0;
}
inline void rotate(int x) {
int fa = f[x], ffa = f[f[x]], wx = get(x);
if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
maintain(fa); maintain(x);
}
void clt(int i) {
static int st[maxn + maxm], top;
st[top = 1] = i;
while (~get(i)) st[++top] = i = f[i];
while (top) push(st[top--]);
}
void Splay(int i) {
clt(i);
for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
if (~get(fa)) rotate(get(i) == get(fa) ? fa : i);
}
void access(int i) { for (int p = 0; i; i = f[p = i]) Splay(i), rc = p, maintain(i); }
inline void make_rt(int i) { access(i); Splay(i); setr(i); }
inline void split(int x, int y) { make_rt(x); access(y); Splay(y); }
int find_rt(int i) { access(i); Splay(i); while (lc) i = lc; return Splay(i), i; }
inline void link(int x, int y) {
if (find_rt(x) == find_rt(y)) return ;
make_rt(x); f[x] = y;
}
inline void cut(int x, int y) {
if (find_rt(x) != find_rt(y)) return ;
split(x, y);
if (T[y].ch[0] == x && !T[x].ch[1])
T[y].ch[0] = f[x] = 0, maintain(y);
}
bool vis[maxm];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w;
sort(e + 1, e + m + 1, [](const Edge &u, const Edge &v) { return u.w < v.w; }); init_LCT();
int num = 0, st = 1, ans = INF;
for (int i = 1; i <= m; ++i) {
int u = e[i].u, v = e[i].v, w = e[i].w; if (u == v) { vis[i] = 1; continue; }
if (find_rt(u) == find_rt(v)) {
split(u, v); int k = T[v].v; vis[k] = 1; --num;
cut(e[k].u, k + n), cut(e[k].v, k + n);
} link(u, i + n), link(v, i + n); ++num;
while (vis[st]) ++st;
if (num == n - 1) ans = min(ans, w - e[st].w);
} cout << ans << "\n";
return 0;
}
|