Luogu4180 严格次小生成树

题目链接

题目

求严格次小生成树的权值。

$1 \leq n \leq 100000, 1 \leq m \leq 300000$

分析

次小生成树可以通过替换掉最小生成树上的一条边得到。

$LCT$ 维护最小生成树,维护一个最大值和次大值。枚举不在最小生成树上的边,用环中最大或次大的边替换。

由于 $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
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
using ll = long long;
struct Edge {
int u, v, w;
bool operator<(const Edge &rhs) const { return w < rhs.w; }
};
vector<Edge> edges;
int n, m;

struct LCT {
int val[maxn], max[maxn], smax[maxn]; // 基于点权
int rev[maxn], ch[maxn][2], fa[maxn];
int stk[maxn];
inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return ch[fa[x]][1] == x; }
inline void reverse(int x) {
swap(ch[x][0], ch[x][1]);
rev[x] ^= 1;
}
inline void pushdown(int x) {
if (rev[x]) {
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
rev[x] ^= 1;
}
}

// 因为儿子可能会改变,因此每次必须重新计算
int tmp[10];
inline void pushup(int x) {
int tot = 0;
tmp[tot++] = val[x];
max[x] = val[x];
if (ch[x][0]) {
tmp[tot++] = max[ch[x][0]];
tmp[tot++] = smax[ch[x][0]];
max[x] = std::max(max[x], max[ch[x][0]]);
}
if (ch[x][1]) {
tmp[tot++] = max[ch[x][1]];
tmp[tot++] = smax[ch[x][1]];
max[x] = std::max(max[x], max[ch[x][1]]);
}
smax[x] = -1;
for (int i = 0; i < tot; i++)
if (tmp[i] < max[x] && tmp[i] > smax[x]) smax[x] = tmp[i];
}
// 避免单独使用:不能直接旋转根
void rotate(int x) {
int y = fa[x], z = fa[y], d = get(x);
if (!isroot(y)) ch[z][get(y)] = x;
fa[x] = z;
ch[y][d] = ch[x][d ^ 1], fa[ch[y][d]] = y;
ch[x][d ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
// 将x旋转到Splay的根
void splay(int x) {
int top = 0;
stk[++top] = x;
for (int i = x; !isroot(i); i = fa[i]) stk[++top] = fa[i];
for (int i = top; i; i--) pushdown(stk[i]);
for (int f; !isroot(x); rotate(x))
if (!isroot(f = fa[x])) rotate(get(x) == get(f) ? f : x);
}

// 将根到x的路径拉到一棵Splay中
void access(int x) {
for (int y = 0; x; y = x, x = fa[x]) splay(x), ch[x][1] = y, pushup(x);
}
// 让x成为原树的根,x为深度最低的点,其左子树为空
void makeroot(int x) { access(x), splay(x), reverse(x); }

// 找x所在原树的根。主要用来判联通性,如果find(x) = find(y)
// 则x,y在同一棵树中。
int find(int x) {
access(x), splay(x);
while (ch[x][0]) pushdown(x), x = ch[x][0];
splay(x);
return x;
}
// 加边,y为深度最低的点(顺序无所谓)
void link(int x, int y) {
makeroot(x);
fa[x] = y, splay(x);
}

// 将x到y的路径拉到一棵Splay中,y为Splay的根
void split(int x, int y) { makeroot(x), access(y), splay(y); }
} lct;

bool vis[maxn];
int par[maxn];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
inline void merge(int x, int y) {
x = find(x);
y = find(y);
par[x] = y;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) par[i] = i;

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
edges.push_back({u, v, w});
}
sort(edges.begin(), edges.end());
int cnt = 0;
ll tot = 0;
for (int i = 0, u, v, w; i < m; i++) {
u = edges[i].u;
v = edges[i].v;
w = edges[i].w;
if (find(u) == find(v)) continue;
merge(u, v);
lct.link(u, i + 1 + n);
lct.link(v, i + 1 + n);
lct.val[i + 1 + n] = w;

cnt++;
tot += w;
vis[i] = true;
if (cnt == n - 1) break;
}
ll ans = 1e18;
for (int i = 0, u, v, w; i < m; i++) {
u = edges[i].u;
v = edges[i].v;
w = edges[i].w;
if (vis[i]) continue;
lct.split(u, v);

ll tmp = tot - lct.max[v] + w;
if (tmp != tot) ans = min(ans, tmp);
tmp = tot - lct.smax[v] + w;
if (tmp != tot) ans = min(ans, tmp);
}
printf("%lld\n", ans);
}