【探究】用LCT维护MST

主要是整理了一下 $\rm LCT$ 维护 $\rm min/max~spanning~tree$ 。

说起来其实很简单,只要维护一条路径中最长的那条边,然后替换即可。

似乎很简单?就是很简单。

LG3366 【模板】最小生成树

就是贴个代码?

值得注意的是,需要把每一条边加入点,删除的话就只需要把与这条边相连的点之间的边断掉。

似乎没啥难的?LCT虽然说很长,但是似乎写起来很轻松诶。

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#define il inline
#define gcr getchar
#define fr(k) e[k].fr
#define to(k) e[k].to
#define vl(k) e[k].vl
#define fa(x) t[x].fa
#define rv(x) t[x].rev
#define lc(x) t[x].son[0]
#define rc(x) t[x].son[1]

using namespace std ;

const int N = 400010 ;
const int M = 600010 ;

struct Edge{
int vl ;
int fr, to ;
}e[M] ;
struct LCT{
int fa ;
int rev ;
int son[2] ;
}t[N] ;
int ans ;
int n, m ;
int val[M] ;
int stk[N], tp ;


void qr(int &x){
x = 0 ; char c = gcr() ;
while (c > '9' || c < '0') c = gcr() ;
while (isdigit(c)) x = x * 10 + c - 48, c = gcr() ;
}
bool notroot(int x){
return ((lc(fa(x)) == x) || (rc(fa(x)) == x)) ;
}
void reverse(int x){
rv(x) ^= 1, swap(lc(x), rc(x)) ;
}
void _down(int x){
if (rv(x)){
rv(x) = 0 ;
if (lc(x)) reverse(lc(x)) ;
if (rc(x)) reverse(rc(x)) ;
}
}
void update(int x){
val[x] = x ;
if (vl(val[x]) < vl(val[lc(x)])) val[x] = val[lc(x)] ;
if (vl(val[x]) < vl(val[rc(x)])) val[x] = val[rc(x)] ;
}
void rotate(int x){
bool w = x == rc(fa(x)) ;
int f1 = fa(x), f2 = fa(f1) ;
if (notroot(f1))
t[f2].son[f1 == rc(f2)] = x ;
t[f1].son[w] = t[x].son[w ^ 1] ;
fa( t[x].son[w ^ 1] ) = f1 ;
fa(x) = f2 ; fa(f1) = x ;
t[x].son[w ^ 1] = f1 ;
update(f1) ;
}
void splay(int x){
int y ;
stk[++ tp] = y = x ;
while (notroot(y))
y = fa(y), stk[++ tp] = y ;
while (tp) _down(stk[tp --]) ;
while (notroot(x)){
int f1 = fa(x) ;
int f2 = fa(f1) ;
if (notroot(f1)){
if ((rc(f1) == x) == (rc(f2) == f1))
rotate(f1) ; else rotate(x) ;
}
rotate(x) ;
}
update(x) ;
}
void access(int x){
int y = 0 ;
for ( ; x ; x = fa(y = x))
splay(x), rc(x) = y, update(x) ;
}
void make_root(int x){
access(x) ;
splay(x) ; reverse(x) ;
}
int find_root(int x){
access(x) ; splay(x) ;
while(lc(x)) x = lc(x) ;
return x ;
}
void split(int u, int v){
make_root(u), access(v), splay(v) ;
}
void link(int u, int v){
make_root(u), fa(u) = v ;
}
void cut(int u, int v){
split(u, v) ;
fa(u) = lc(v) = 0 ;
update(v) ;
}
void cut(int x){
//access(to(x)) ;
splay(x) ;
lc(x) = rc(x) = fa(lc(x)) = fa(rc(x)) = 0 ;
update(x) ;
}
int main(){
cin >> n >> m ;
for (int i = 1 ; i <= m ; ++ i){
qr(fr(i)),
qr(to(i)), qr(vl(i)) ;
//cout << vl(i) << endl ;
fr(i) += m, to(i) += m ;
make_root(to(i)) ;
if (find_root(fr(i)) != to(i))
ans += vl(i), link(fr(i), i), link(to(i), i) ;
else if (vl(i) < vl(val[fr(i)])){
ans += vl(i) - vl(val[fr(i)]) ;
cut(val[fr(i)]), link(fr(i), i), link(to(i), i) ;
}
//cout << ans << endl ;
}
cout << ans << endl ; return 0 ;
}

[WC2006]水管局长

要求动态维护一张图。

只有删边操作、动态询问 $x$ 到 $y$ 间所有路径上最大边权的最小值。

那显然是在最小生成树上跑。

既有加边也有删边的MST是没法做的。因为删边的时候可能有一堆候选集合,这是无法简单维护的。但是只有加边或者只有删边的MST很简单。由于只有删边,所以倒着做一遍就完了。

hiahiahia,快来欣赏一下我特别棒的码风:

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
int main(){
int o, u, v ;
cin >> n >> m >> q ;
for (int i = 1 ; i <= m ; ++ i){
qr(fr(i)) ;
qr(to(i)) ;
qr(vl(i)) ;
fr(i) += (m + q) ;
to(i) += (m + q) ;
if (fr(i) > to(i))
swap(fr(i), to(i)) ;
Id[mk_p(fr(i), to(i))] = i ;
}
for (int i = m + 1 ; i <= m + q ; ++ i){
qr(vl(i)) ;
qr(fr(i)) ;
qr(to(i)) ;
fr(i) += (m + q) ;
to(i) += (m + q) ;
int u = fr(i) ;
int v = to(i) ;
if (vl(i) <= 1) continue ;
if (u > v)
swap(u, v),
swap(fr(i), to(i)) ;
o = Id[mk_p(u, v)] ;
vis[o] = 1, mem[i] = o ;
}
//cout << 2333 << endl ;
for (int i = 1 ; i <= m ; ++ i){
if (vis[i])
continue ;
u = fr(i) ;
v = to(i) ;
make_root(v) ;
if (find_root(u) != v){
link(u, i) ;
link(v, i) ;
}
else if (vl(i) < vl(val[u])){
dcut(val[u]) ;
link(u, i) ; link(v, i) ;
}
}
for (int i = m + q ; i > m ; -- i){
int u = fr(i) ;
int v = to(i) ;
int j = mem[i] ;
if (vl(i) == 1){
merge(u, v) ;
ans[i - m] = vl(val[v]) ;
}
else{
u = fr(j) ;
v = to(j) ;
make_root(v) ;
ans[i - m] = -1 ;
if (find_root(u) != v){
link(u, j) ;
link(v, j) ;
}
else if (vl(j) < vl(val[fr(j)])){
dcut(val[u]) ;
link(u, j) ; link(v, j) ;
}
}
}
for (int i = 1 ; i <= q ; ++ i)
if (~ans[i]) printf("%d\n", ans[i]) ;
return 0 ;
}

[NOI2014]魔法森林

给出一个 $n$ 个点,$m$ 条边的无向图,每条边都有权值 $a_i,b_i$ 。

求一条从点 $1$ 到点 $n$ 的路径,使得这条路径上边的 $a_i,b_i$ 最大值之和最小。

$2 \leq n \leq 5 \times 10^4, 0 \leq m \leq 1 \times 10^5$。

发现可以先把边权按照第一维排个序,然后做普通的lct维护MST就完了。

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
int main(){
cin >> n >> m ; ans = MAX ;
for (int i = 1 ; i <= m ; ++ i)
qr(fr(i)), qr(to(i)), qr(va(i)), qr(vb(i)) ;
for (int i = 1 ; i <= m ; ++ i) fr(i) += m, to(i) += m ;
for (int i = 1 ; i <= n + m + 1 ; ++ i) f[i] = i ;
sort(E + 1, E + m + 1, comp) ;
for (int i = 1 ; i <= m ; ++ i){
rg int f1, f2 ;
rg int u = fr(i), v = to(i) ;
if (u == v) continue ;
//cout << val[i] << endl ;
merge(v, u) ;
f1 = find(u), f2 = find(v) ;
//cout << f1 << " " << f2 << endl ;
if (f1 != f2){
link(u, i), link(v, i) ;
if (sz[f1] < sz[f2])
f[f1] = f2, sz[f2] += sz[f1] ;
else f[f2] = f1, sz[f1] += sz[f2] ;
}
else if (vb(i) < vb(val[u]))
cut(val[u]), link(u, i), link(v, i) ;
if (find(m + 1) == find(m + n))
merge(m + 1, n + m),
ans = Min(ans, va(i) + vb(val[n + m]) ) ;
}
cout << (ans == MAX ? -1 : ans) << endl ; return 0 ;
}

总结

我在水博客。