正文
Luogu 4234 最小差值生成树 - LCT 维护链信息
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
Solution
将边从小到大排序, 添新边$(u, v)$时 若$u,v$不连通则直接添, 若连通则 把链上最小的边去掉 再添边。
若已经加入了 $N - 1$条边则更新答案。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std;
const int N = 1e5 + ;
const int inf = 1e9;
int n, m, ans = inf;
int vis[N << ];
struct edge {
int u, v, w;
}e[N << ];
int cmp(const edge &A, const edge &B) {
return A.w < B.w;
}
int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
}
void cmin(int &A, int B) {
if (A > B)
A = B;
}
namespace LCT {
int val[N << ], ch[N << ][], f[N << ], mx[N << ], tun[N << ];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
int isroot(int x) {
return lc(f[x]) != x && rc(f[x]) != x;
}
int get(int x) {
return rc(f[x]) == x;
}
void up(int x) {
mx[x] = val[x];
if (e[mx[lc(x)]].w < e[mx[x]].w) mx[x] = mx[lc(x)];
if (e[mx[rc(x)]].w < e[mx[x]].w) mx[x] = mx[rc(x)];
}
void rev(int x) {
swap(lc(x), rc(x));
tun[x] ^= ;
}
void pushdown(int x) {
if (tun[x]) {
if (lc(x)) rev(lc(x));
if (rc(x)) rev(rc(x));
tun[x] = ;
}
}
int st[N << ], tp;
void pd(int x) {
while (!isroot(x)) {
st[++tp] = x;
x = f[x];
}
pushdown(x);
while (tp) pushdown(st[tp--]);
}
void rotate(int x) {
int old = f[x], oldf = f[old], son = ch[x][get(x) ^ ];
if (!isroot(old)) ch[oldf][get(old)] = x;
ch[x][get(x) ^ ] = old;
ch[old][get(x)] = son;
f[old] = x; f[x] = oldf; f[son] = old;
up(old); up(x);
}
void splay (int x) {
pd(x);
for (; !isroot(x); rotate(x))
if (!isroot(f[x]))
rotate(get(f[x]) == get(x) ? f[x] : x);
}
void access(int x) {
for (int y = ; x; y = x, x = f[x])
splay(x), ch[x][] = y, up(x);
}
void mroot(int x) {
access(x); splay(x); rev(x);
}
void split(int x, int y) {
mroot(x); access(y); splay(y);
}
int findr(int x) {
access(x); splay(x);
while (lc(x)) pushdown(x), x = lc(x);
return x;
}
void link(int x, int y) {
mroot(x); f[x] = y;
}
void cut(int x, int y) {
split(x, y);
f[x] = ch[y][] = ;
}
}
using namespace LCT;
int main()
{
n = rd; m = rd;
e[].w = inf;
for (int i = ; i <= m; ++i) {
e[i].u = rd; e[i].v = rd; e[i].w = rd;
}
sort(e + , e + + m, cmp);
for (int i = ; i <= m; ++i)
val[i + n] = i;
for (int i = , l = , tot = ; i <= m; ++i) {
int x = e[i].u, y = e[i].v;
if (x == y) continue;
mroot(x);
if (findr(y) != x) {
link(i + n, y);
link(i + n, x);
vis[i] = ;
tot++;
if (tot == n - ) {
while (!vis[l]) l++;
cmin(ans, e[i].w - e[l].w);
}
}
else {
int t = mx[y];
cut(t + n, e[t].u);
cut(t + n, e[t].v);
link(i + n, x);
link(i + n, y);
vis[t] = ; vis[i] = ;
if (tot == n - ) {
while (!vis[l]) l++;
cmin(ans, e[i].w - e[l].w);
}
}
}
printf("%d\n", ans);
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
using namespace std; const int N = 1e5 + ;
const int inf = 1e9; int n, m, ans = inf;
int vis[N << ]; struct edge {
int u, v, w;
}e[N << ]; int cmp(const edge &A, const edge &B) {
return A.w < B.w;
} int read() {
int X = , p = ; char c = getchar();
for (; c > '' || c < ''; c = getchar())
if (c == '-') p = -;
for (; c >= '' && c <= ''; c = getchar())
X = X * + c - '';
return X * p;
} void cmin(int &A, int B) {
if (A > B)
A = B;
} namespace LCT {
int val[N << ], ch[N << ][], f[N << ], mx[N << ], tun[N << ];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1] int isroot(int x) {
return lc(f[x]) != x && rc(f[x]) != x;
} int get(int x) {
return rc(f[x]) == x;
} void up(int x) {
mx[x] = val[x];
if (e[mx[lc(x)]].w < e[mx[x]].w) mx[x] = mx[lc(x)];
if (e[mx[rc(x)]].w < e[mx[x]].w) mx[x] = mx[rc(x)];
} void rev(int x) {
swap(lc(x), rc(x));
tun[x] ^= ;
} void pushdown(int x) {
if (tun[x]) {
if (lc(x)) rev(lc(x));
if (rc(x)) rev(rc(x));
tun[x] = ;
}
} int st[N << ], tp; void pd(int x) {
while (!isroot(x)) {
st[++tp] = x;
x = f[x];
}
pushdown(x);
while (tp) pushdown(st[tp--]);
} void rotate(int x) {
int old = f[x], oldf = f[old], son = ch[x][get(x) ^ ];
if (!isroot(old)) ch[oldf][get(old)] = x;
ch[x][get(x) ^ ] = old;
ch[old][get(x)] = son;
f[old] = x; f[x] = oldf; f[son] = old;
up(old); up(x);
} void splay (int x) {
pd(x);
for (; !isroot(x); rotate(x))
if (!isroot(f[x]))
rotate(get(f[x]) == get(x) ? f[x] : x);
} void access(int x) {
for (int y = ; x; y = x, x = f[x])
splay(x), ch[x][] = y, up(x);
} void mroot(int x) {
access(x); splay(x); rev(x);
} void split(int x, int y) {
mroot(x); access(y); splay(y);
} int findr(int x) {
access(x); splay(x);
while (lc(x)) pushdown(x), x = lc(x);
return x;
} void link(int x, int y) {
mroot(x); f[x] = y;
} void cut(int x, int y) {
split(x, y);
f[x] = ch[y][] = ;
}
}
using namespace LCT; int main()
{
n = rd; m = rd;
e[].w = inf;
for (int i = ; i <= m; ++i) {
e[i].u = rd; e[i].v = rd; e[i].w = rd;
}
sort(e + , e + + m, cmp);
for (int i = ; i <= m; ++i)
val[i + n] = i;
for (int i = , l = , tot = ; i <= m; ++i) {
int x = e[i].u, y = e[i].v;
if (x == y) continue;
mroot(x);
if (findr(y) != x) {
link(i + n, y);
link(i + n, x);
vis[i] = ;
tot++;
if (tot == n - ) {
while (!vis[l]) l++;
cmin(ans, e[i].w - e[l].w);
}
}
else {
int t = mx[y];
cut(t + n, e[t].u);
cut(t + n, e[t].v);
link(i + n, x);
link(i + n, y);
vis[t] = ; vis[i] = ;
if (tot == n - ) {
while (!vis[l]) l++;
cmin(ans, e[i].w - e[l].w);
}
}
}
printf("%d\n", ans);
}