最小生成树 / MST
stripe_python · · 算法·理论
LCT 求法
对连通无向图
- 以任意顺序枚举
e \in E ,将e 加入E(T) 。 - 若
e 加入后成环,删去环上的最大边。
使用 LCT 维护
Kruskal
对
若
对于
Prim
选取任意顶点
由于
Boruvka
初始将
每轮操作中,同时考虑当前所有连通块,找出从块内出发连向其他块的最小边。将所有最小边同时加入
若边权互不相同,则合并过程不会成环,且每轮连通块数目折半,只会执行
下面给出模板题的 Boruvka 写法。
:::::info[代码]
const int N = 2e5 + 5, inf = 1e9;
int n, m, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
using info = pair<int, int>;
vector<pair<int, info>> e[N];
pair<info, int> out[N];
i64 boruvka() {
iota(fa + 1, fa + n + 1, 1);
i64 res = 0;
for (int cnt = 0; cnt < n - 1; ) {
fill(out + 1, out + n + 1, make_pair(info{inf, -1}, -1));
for (int u = 1; u <= n; u++)
for (auto [v, w] : e[u]) {
if (find(u) == find(v)) continue;
if (w < out[find(u)].fi) out[find(u)] = {w, v};
}
for (int u = 1; u <= n; u++) {
if (u != find(u) || out[u].se == -1) continue;
int fu = u, fv = find(out[u].se);
if (fu != fv) fa[fu] = fv, cnt++, res += out[u].fi.fi;
}
} return res;
}
void _main() {
cin >> n >> m;
iota(fa + 1, fa + n + 1, 1);
for (int i = 1, u, v, c; i <= m; i++) {
cin >> u >> v >> c; info w(c, i);
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
fa[find(u)] = find(v);
}
int cnt = 0;
for (int i = 1; i <= n; i++) if (i == find(i)) cnt++;
if (cnt > 1) return cout << "orz", void();
cout << boruvka();
}
:::::
Kruskal 重构树
在 Kruskal 过程中,设边
可以发现下列性质:
- Kruskal 重构树是一棵二叉树,叶子对应原图顶点。
- 每个点根链上点权单调递增。
- 原图两顶点的最小瓶颈路,等价于 Kruskal 重构树上两点 LCA 的点权。
LP 形式
MST 可以写成如下 LP 问题:
上面的式子中:
-
-
-
- 不需要添加
x_e \in \{0,1\} 的约束。可以证明,上述 LP 问题是完全整的。
得到 MST 问题具有凸性,可以使用凸优化等方法求解。
练习
P14362 [CSP-S 2025] 道路修复
给定
n 个点m 条边的无向连通图G=(V,E) ,边带权。现有
k 种决策,第i 种决策新建顶点x ,对所有u \in V 连边u \leftrightarrow x ,边权为a_{i,u} 。选择第i 种决策需要c_i 的代价。你可以选择任意决策,代价定义为新图 MST 边权和加上所选决策的总代价。最小化代价并输出。
:::::success[题解]
注意到
设
注意到 Kruskal 的瓶颈在排序,考虑将子图的边先排序,枚举时归并优化。复杂度
据说有
:::::
:::::info[代码]
const int N = 1e4 + 15, M = 1e6 + 5;
int n, m, k, c[15];
struct dsu {
int fa[N], sz[N];
void init() {iota(fa, fa + n+k + 1, 0), fill(sz, sz + n+k + 1, 1);}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz[x] > sz[y]) swap(x, y);
return fa[x] = y, sz[y] += sz[x], true;
}
} U;
struct edge {
int u, v, w;
edge(int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
bool operator< (const edge& o) const {return w < o.w;}
} g[M], e[15][N], h[11*N], tmp[11*N];
void _main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
sort(g + 1, g + m + 1); U.init();
int cnt = 0;
for (int i = 1; i <= m; i++) {
auto [u, v, w] = g[i];
if (U.unite(u, v)) e[0][++cnt] = {u, v, w};
}
for (int i = 1; i <= k; i++) {
cin >> c[i];
for (int u = 1, w; u <= n; u++) cin >> w, e[i][u] = {i+n, u, w};
sort(e[i] + 1, e[i] + n + 1);
}
i64 res = 1e18;
for (int s = 0; s < (1 << k); s++) {
copy(e[0] + 1, e[0] + n, h + 1);
i64 cur = 0, cnt = n - 1;
for (int i = 1; i <= k; i++) if (s >> (i - 1) & 1) {
cur += c[i];
merge(h + 1, h + cnt + 1, e[i] + 1, e[i] + n + 1, tmp + 1);
cnt += n, copy(tmp + 1, tmp + cnt + 1, h + 1);
}
U.init();
for (int i = 1; i <= cnt; i++) {
auto [u, v, w] = h[i];
if (U.unite(u, v)) cur += w;
}
chkmin(res, cur);
}
cout << res;
}
:::::
CF2081D MST in Modulo Graph
给定
n 个点的完全图,边(i,j) 的权值为\max(a_i,a_j) \bmod \min(a_i,a_j) 。求最小生成树边权和。多测,
\sum n, \sum \max a_i \le 5 \times 10^5 ,3 秒,500 MB。
ZR3598 没啥题
给定
n 个区间[l_i,r_i] ,任意两个区间(i,j) 有边,边权为[l_i,r_i] \cap [l_j,r_j] 的长度。求最小生成树边权和。多测,
\sum n \le 2 \times 10^6 ,1 秒,512 MB。
:::::success[题解]
考察 Boruvka 的初轮,我们需要对每个区间
假定交集非空,对
我们希望
- 最小化
r_i-l_j 取l_j 最大的区间x 。 - 最小化
r_j-l_i 取r_j 最小的区间y 。 - 最小化
r_j-l_j 取r_j-l_j 最小的区间z 。
这里我们丢掉
考虑一轮 Boruvka 后得到的最小边。除
我们注意到,这种形态的图只需要一轮 Boruvka 就能得到 MST!可以从三元环的情形类比过来。
于是直接找出每个区间的最小边相加即可,复杂度
:::::
:::::info[代码]
const int N = 2e6 + 5, inf = 1e9;
int n, l[N], r[N];
i64 f(int l1, int r1, int l2, int r2) {
return max(0, min(r1, r2) - max(l1, l2));
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
int x = max_element(l + 1, l + n + 1) - l;
int y = min_element(r + 1, r + n + 1) - r;
i64 z = inf;
for (int i = 1; i <= n; i++) chkmin<i64>(z, r[i] - l[i]);
i64 res = 0;
for (int i = 1; i <= n; i++) {
if (i == x) continue;
res += min({z, f(l[i], r[i], l[x], inf), f(l[i], r[i], -inf, r[y])});
}
cout << res << '\n';
}
:::::
AT_cf17_final_j Tree MST
给定一棵
n 个点的无根树,边带权,第i 个节点的点权为a_i 。构造
n 个点的完全图,边(u,v) 的权值为a_u+a_v+\text{dis}(u,v) ,其中\text{dis}(u,v) 为树链u \to v 的边权和。求最小生成树边权和。
:::::success[题解]
任意定根后,记
令
转而枚举
考虑做换根 DP:
- 对每个
x 维护a_v-2d_x 的最小值,其中v \in \text{subtree}(x) 。自底向上一次 DFS。 - 对每个
u 用(a_v-2d_x)_{\min} 更新最小边,其中u \in \text{subtree}(x) 。自顶向下一次 DFS。
还有一个约束需要考虑,上述过程最终求得的
解决方法是,我们同时记录最小值和次小值,并钦定最小值对应的
根据 Boruvka 进行
:::::
:::::info[代码]
const int N = 2e5 + 5;
const i64 inf = 1e18;
i64 n, a[N], d[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<pair<int, int>> e[N];
void dfs1(int u, int fa) {
for (auto [v, w] : e[u]) if (v != fa) d[v] = d[u] + w, dfs1(v, u);
}
using info = pair<i64, int>; // (w, id)
struct node {
info a, b; int c;
node() : a(inf, -1), b(inf, -1), c(-1) {}
};
node operator+ (const node& x, const node& y) {
node z;
if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
return z;
}
node f[N];
void dfs2(int u, int fa) {
f[u].a = {a[u], u}, f[u].c = find(u);
for (auto [v, w] : e[u]) if (v != fa)
dfs2(v, u), f[u] = f[u] + f[v];
}
void dfs3(int u, int fa) {
for (auto [v, w] : e[u]) if (v != fa)
f[v] = f[v] + f[u], dfs3(v, u);
}
info out[N];
i64 boruvka() {
iota(fa + 1, fa + n + 1, 1);
i64 res = 0;
for (int cnt = 0; cnt < n - 1; ) {
fill(f + 1, f + n + 1, node{}), fill(out + 1, out + n + 1, info{inf, -1});
dfs2(1, -1);
for (int u = 1; u <= n; u++) f[u].a.fi -= 2*d[u], f[u].b.fi -= 2*d[u];
dfs3(1, -1);
for (int u = 1; u <= n; u++) {
info x = f[u].c == find(u) ? f[u].b : f[u].a;
chkmin(out[find(u)], {x.fi + a[u], x.se});
}
for (int u = 1; u <= n; u++) {
if (u != find(u) || out[u].se == -1) continue;
int fu = u, fv = find(out[u].se);
if (fu != fv) fa[fu] = fv, cnt++, res += out[u].fi;
}
}
return res;
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
dfs1(1, -1);
for (int i = 1; i <= n; i++) a[i] += d[i];
cout << boruvka();
}
:::::
CF888G Xor-MST
给定
n 个顶点,第i 个点的点权为a_i 。构造n 个点的完全图,边(u,v) 的权值为a_u \oplus a_v 。求最小生成树边权和。
:::::success[题解]
考虑 Boruvka,将问题转化成寻找最小边。
异或最优化问题,考虑自高位向低位建立 01-Trie。对全局维护 01-Trie
对
合并两个连通块时,直接对 01-Trie 进行合并即可。维护信息需要
注意 Boruvka 要求不出现边权相等的边。对于
:::::
:::::info[代码]
const int N = 2e5 + 5, inf = 2e9;
using info = pair<int, int>;
int n, a[N], fa[N]; info out[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int tot, T[N], ch[2][65*N], cnt[65*N], id[65*N];
void pushup(int u) {cnt[u] = cnt[ch[0][u]] + cnt[ch[1][u]];}
void insert(int& u, int x, int p, int d = 30) {
if (!u) u = ++tot;
if (d < 0) return cnt[u]++, id[u] = p, void();
insert(ch[x >> d & 1][u], x, p, d - 1), pushup(u);
}
int merge(int u, int v, int d = 30) {
if (!u || !v) return u ? u : v;
if (d < 0) return cnt[u] += cnt[v], u;
ch[0][u] = merge(ch[0][u], ch[0][v], d - 1);
ch[1][u] = merge(ch[1][u], ch[1][v], d - 1);
return cnt[u] += cnt[v], u;
}
info ask(int u, int v, int x, int s = 0, int d = 30) {
if (d < 0) return {s, id[u]};
int t = x >> d & 1;
if (cnt[ch[t][u]] - cnt[ch[t][v]]) return ask(ch[t][u], ch[t][v], x, s, d - 1);
return ask(ch[t ^ 1][u], ch[t ^ 1][v], x, s | (1 << d), d - 1);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
return fa[v] = u, T[u] = merge(T[u], T[v]), true;
}
void _main() {
cin >> n; iota(fa + 1, fa + n + 1, 1);
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) - a - 1;
for (int i = 1; i <= n; i++) insert(T[0], a[i], i), insert(T[i], a[i], i);
i64 res = 0;
for (int cnt = 0; cnt < n-1; ) {
fill(out + 1, out + n + 1, info{inf, -1});
for (int u = 1; u <= n; u++)
chkmin(out[find(u)], ask(T[0], T[find(u)], a[u]));
for (int u = 1; u <= n; u++) {
if (u != find(u) || out[u].se == -1) continue;
if (unite(u, out[u].se)) res += out[u].fi, cnt++;
}
} cout << res;
}
:::::
CF2081D MST in Modulo Graph
给定
n 个点的完全图,边(i,j) 的权值为\max(a_i,a_j) \bmod \min(a_i,a_j) 。求最小生成树边权和。多测,
\sum n, \sum \max a_i \le 5 \times 10^5 ,3 秒,500 MB。
:::::success[题解]
直接 Boruvka,问题变为给定
丢掉不同色的限制是套路的,维护最小值和次小值,并钦定二者颜色不同,信息构成交换半群。
设
-
若
a_i=x ,最小化a_j \bmod x 。枚举k=x,2x,3x,\cdots ,在区间[k,k+x) 中a_j \bmod x=a_j-k ,区间查询权值\min 即可。
进一步,权值\ge k+x 的点必然更劣,不会影响答案。预处理后缀信息并,直接做k 的后缀查询即可。 -
若
a_i=y ,最小化y \bmod a_j=y-\lfloor \frac{y}{x}\rfloor x 。
离线对x=a_j 枚举k=x,2x,3x,\cdots ,将j 挂在k 处,权值为-k 。
再对y 扫描线,每个j 最后被扫描的时刻恰为\lfloor \frac{y}{a_j}\rfloor \times a_j 。直接维护\min(-k) ,权值+y 即为所求。
注意实现细节,需要将值相等的
加上 boruvka 一只
:::::
:::::info[代码]
const int N = 5e5 + 5, inf = 1e9;
int n, m, a[N], c[N], fa[N];
vector<int> pos[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
return fa[x] = y, true;
}
using info = pair<int, int>; // (权值, 节点标号)
struct node { // a 是最小值,b 是次小值
info a, b; int c;
node() : a(inf, -1), b(inf, -1), c(-1) {}
node(info x) : a(x), b(inf, -1), c(find(x.se)) {}
info get(int c0) {return c != c0 ? a : b;}
};
const node I{};
node operator+ (const node& x, const node& y) {
// 半群复合
if (x.a.se == -1) return y;
if (y.a.se == -1) return x;
node z;
if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
return z;
}
node operator- (node x, int k) { // 权值 -k
return x.a.fi -= k, x.b.fi -= k, x;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
node val[N], suf[N], wei[N];
// val[x]: a_i=x 的 i 信息并
// suf[x]: val 的后缀和
// wei[x]: 挂在 x 的 (-k, j) 信息并
info ans[N], out[N];
// ans[u]: 与节点 u 不同块的最小边
// out[u]: u 块向外的最小边
void solve() {
fill(val + 1, val + m + 1, I);
for (int i = 1; i <= n; i++) val[a[i]] += info(a[i], i);
copy(val + 1, val + m + 1, suf + 1);
for (int i = m-1; i >= 1; i--) suf[i] += suf[i+1];
fill(ans + 1, ans + n + 1, info(inf, -1));
for (int x = 1; x <= m; x++) {
if (pos[x].empty()) continue;
node cur = I;
for (int k = x; k <= m; k += x) cur += suf[k] - k;
for (int i : pos[x]) chkmin(ans[i], cur.get(find(i)));
}
fill(wei + 1, wei + m + 1, I);
for (int x = 1; x <= m; x++)
for (int k = x; k <= m; k += x) wei[k] += val[x] - (x + k);
node cur = I;
for (int y = 1; y <= m; y++) {
cur += wei[y];
for (int i : pos[y]) {
auto [w, j] = cur.get(find(i));
chkmin(ans[i], info(w + y, j));
}
}
}
void _main() {
cin >> n; iota(fa + 1, fa + n + 1, 1);
for (int i = 1; i <= n; i++) cin >> a[i];
m = *max_element(a + 1, a + n + 1);
for (int i = 1; i <= m; i++) pos[i].clear();
for (int i = 1; i <= n; i++) pos[a[i]].pb(i);
i64 res = 0;
for (int cnt = 0; cnt < n-1; ) { // boruvka 过程
solve();
fill(out + 1, out + n + 1, info(inf, -1));
for (int u = 1; u <= n; u++) chkmin(out[find(u)], ans[u]);
for (int u = 1; u <= n; u++) {
if (u != find(u)) continue;
info q = out[u];
if (unite(u, q.se)) cnt++, res += q.fi;
}
}
cout << res << '\n';
}
:::::
:::::success[另解]
对
将点权相同的点缩起来处理,复杂度是调和型枚举,只会建
:::::
P9701 [GDCPC 2023] Classic Problem
构造
n 个点的完全图,其中m 条特殊边的边权给定,剩余边(i,j) 的权值为|i-j| 。求最小生成树边权和。多测,
n \le 10^9 ,m \le 10^5 ,\sum m \le 5 \times 10^5 ,8 秒,1024 MB。
:::::success[题解]
将特殊边的端点记为特殊点。在数轴上考虑问题,对于两个相邻的特殊点
我们将
考虑 Boruvka。对于点
- 从
u 出发的特殊边。 - 在
u 左侧最近的异块点v 连边(u,v) ,满足u\to v 无特殊边。 - 在
u 右侧最近的异块点v 连边(u,v) ,满足u \to v 无特殊边。
特殊边容易处理。后两种情形是对称的,这里只说明左侧点如何处理。
我们在 Boruvka 的每轮中,维护
考虑特殊边只有
:::::
:::::info[代码]
const int N = 4e5 + 5, inf = 2e9;
int n, m, k, a[N], fa[N], lo[N], hi[N], f[N], g[N], pos[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<pair<int, int>> e[N];
set<pair<int, int>> S;
vector<tuple<int, int, int>> vec;
umap<int, int> mp;
using info = pair<int, int>; // (w, id)
info out[N];
void _main() {
S.clear(), vec.clear(), mp.clear();
for (int i = 1; i <= k; i++) e[i].clear();
cin >> n >> m;
a[1] = 1, a[2] = n, n = 2, k = 0;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
vec.emplace_back(u, v, w);
a[++n] = u, a[++n] = v;
}
i64 res = 0;
sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) - a - 1;
mp[a[1]] = ++k, lo[k] = hi[k] = a[1];
for (int i = 2; i <= n; i++) {
int x = a[i - 1], y = a[i];
if (y - x > 1) res += y - x - 2, k++, lo[k] = x + 1, hi[k] = y - 1;
mp[a[i]] = ++k, lo[k] = hi[k] = a[i];
}
for (auto [u, v, w] : vec) {
u = mp[u], v = mp[v];
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
S.emplace(u, v), S.emplace(v, u);
}
iota(fa + 1, fa + k + 1, 1);
for (int cnt = 0; cnt < k-1; ) {
fill(f + 1, f + k + 1, 0), fill(g + 1, g + k + 1, k+1), fill(out + 1, out + k + 1, info{inf, -1});
for (int i = 2; i <= k; i++) {
if (find(i) == find(i - 1)) f[i] = f[i - 1];
else f[i] = i - 1;
}
for (int i = k - 1; i >= 1; i--) {
if (find(i) == find(i + 1)) g[i] = g[i + 1];
else g[i] = i + 1;
}
for (int u = 1; u <= k; u++)
for (auto [v, w] : e[u])
if (find(u) != find(v)) chkmin(out[find(u)], info{w, v});
for (int u = 1; u <= k; u++) {
int v = f[u];
while (v >= 1) {
if (!S.count(make_pair(u, v))) break;
if (--v >= 1 && find(u) == find(v)) v = f[v];
}
if (v >= 1) chkmin(out[find(u)], info{lo[u] - hi[v], v});
}
for (int u = 1; u <= k; u++) {
int v = g[u];
while (v <= k) {
if (!S.count(make_pair(u, v))) break;
if (++v <= k && find(u) == find(v)) v = g[v];
}
if (v <= k) chkmin(out[find(u)], info{lo[v] - hi[u], v});
}
for (int u = 1; u <= k; u++) {
if (u != find(u) || out[u].se == -1) continue;
int fu = u, fv = find(out[u].se);
if (fu != fv) fa[fv] = fu, cnt++, res += out[u].fi;
}
}
cout << res << '\n';
}
:::::
P11134 【MX-X5-T6】「GFOI Round 1」Abiogenesis
给定
n 条线段[l_i,r_i] ,第i 条线段的权值为(a_i,b_i) 。构造无向图
G ,对所有1 \le i<j \le n ,若[l_i,r_i] \cap [l_j,r_j ]\ne \varnothing ,则连边(i,j) ,边权为a_i+a_j+|b_i-b_j| 。求G 最小生成树边权和,或报告G 不连通。多测,
\sum n \le 10^5 ,5 秒,512 MB。
:::::success[题解]
考虑优化 Boruvka 寻找最小边的过程。设第
注意到 AT_cf17_final_j 的 trick,我们同时记录最小值和次小值,并钦定二者对应的
接下来,尝试对绝对值分类讨论。这里以
按
取巧的方法是,直接将
用线段树维护即可,总复杂度
本题极度卡常。下面放的是被卡常的代码,扔给 GPT5.6 卡到了 4.58s 通过。
:::::
:::::info[代码]
const int N = 2e5 + 5, inf = 1e9;
int n, m, d[N], fa[N], sz[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz[x] > sz[y]) swap(x, y);
return fa[x] = y, sz[y] += sz[x], true;
}
struct seg {
int l, r, a, b, id;
} a[N];
using info = pair<int, int>;
struct node {
info a, b; int c;
node() : a(inf, -1), b(inf, -1), c(-1) {}
node(int w, int id) : a(w, id), b(inf, -1), c(find(id)) {}
};
const node I{};
node operator+ (const node& x, const node& y) {
if (x.a.se == -1) return y;
if (y.a.se == -1) return x;
node z;
if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
return z;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
info out[N];
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
node val[4*N], tag[4*N];
void pushup(int rt) {val[rt] = val[ls] + val[rs] + tag[rt];}
void build(int l = 1, int r = m, int rt = 1) {
val[rt] = tag[rt] = I;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
void update(int tl, int tr, const node& c, int l = 1, int r = m, int rt = 1) {
if (tl <= l && r <= tr) return val[rt] += c, tag[rt] += c, void();
int mid = (l + r) >> 1;
if (tl <= mid) update(tl, tr, c, l, mid, ls);
if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
node ask(int tl, int tr, int l = 1, int r = m, int rt = 1) {
if (tl <= l && r <= tr) return val[rt];
int mid = (l + r) >> 1; node res = tag[rt];
if (tl <= mid) res += ask(tl, tr, l, mid, ls);
if (tr > mid) res += ask(tl, tr, mid + 1, r, rs);
return res;
}
} T;
void _main() {
read(n), m = 0;
for (int i = 1; i <= n; i++) {
read(a[i].l, a[i].r, a[i].a, a[i].b), a[i].id = i;
d[++m] = a[i].l, d[++m] = a[i].r;
}
sort(d + 1, d + m + 1), m = unique(d + 1, d + m + 1) - d - 1;
for (int i = 1; i <= n; i++) {
a[i].l = lower_bound(d + 1, d + m + 1, a[i].l) - d;
a[i].r = lower_bound(d + 1, d + m + 1, a[i].r) - d;
}
sort(a + 1, a + n + 1, [](const seg& x, const seg& y) -> bool {
return x.b > y.b;
});
iota(fa + 1, fa + n + 1, 1), fill(sz + 1, sz + n + 1, 1);
i64 res = 0;
for (int cnt = 0; cnt < n-1; ) {
fill(out + 1, out + n + 1, info{inf, -1});
T.build();
for (int i = 1; i <= n; i++) {
node x = T.ask(a[i].l, a[i].r);
if (x.a.se != -1) x.a.fi += a[i].a - a[i].b;
if (x.b.se != -1) x.b.fi += a[i].a - a[i].b;
chkmin(out[find(a[i].id)], x.c == find(a[i].id) ? x.b : x.a);
T.update(a[i].l, a[i].r, node(a[i].a + a[i].b, a[i].id));
}
T.build();
for (int i = n; i >= 1; i--) {
node x = T.ask(a[i].l, a[i].r);
x.a.fi += a[i].a + a[i].b, x.b.fi += a[i].a + a[i].b;
chkmin(out[find(a[i].id)], x.c == find(a[i].id) ? x.b : x.a);
T.update(a[i].l, a[i].r, node(a[i].a - a[i].b, a[i].id));
}
for (int u = 1; u <= n; u++) {
if (u != find(u)) continue;
if (out[u].se == -1) return cout << -1 << '\n', void();
if (unite(u, out[u].se)) cnt++, res += out[u].fi;
}
}
cout << res << '\n';
}
:::::
P6199 [EER1] 河童重工
给定两棵
n 个节点的无根树T_1,T_2 ,边带权。构造
n 个点的完全图,边(u,v) 的权值为\text{dis}_1(u,v)+\text{dis}_2(u,v) 。求最小生成树边权和。
:::::success[题解]
考虑优化 Boruvka 寻找最小边的过程。我们需要为所有顶点
套路地记录最小值和次小值,并钦定二者不同块,则
任意定根后,在
对点集
限制同理放宽为
复杂度与每轮建立的
Boruvka,点分治,建虚树各一只
正确实现的复杂度为
:::::
:::::info[代码]
const int N = 1e5 + 5, inf = 2e9;
int n, a[N], b[N], w[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
x = find(x), y = find(y);
return x == y ? false : (fa[x] = y, true);
}
vector<pair<int, int>> e1[N], e2[N];
void dfs1(int u, int fa) {
for (auto [v, w] : e1[u]) if (v != fa) a[v] = a[u] + w, dfs1(v, u);
}
int dn, dfn[N], st[18][N];
int cmp(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
int lca(int u, int v) {
if (u == v) return u;
if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int k = lg(v - u++);
return cmp(st[k][u], st[k][v - (1 << k) + 1]);
}
void dfs2(int u, int fa) {
dfn[u] = ++dn, st[0][dn] = fa;
for (auto [v, w] : e2[u]) if (v != fa) b[v] = b[u] + w, dfs2(v, u);
}
int del[N], sz[N];
void dfs3(int u, int fa) {
sz[u] = 1;
for (auto [v, w] : e1[u]) if (v != fa && !del[v]) dfs3(v, u), sz[u] += sz[v];
}
int dfs4(int u, int fa, int n) {
for (auto [v, w] : e1[u]) if (v != fa && !del[v] && sz[v] > n/2) return dfs4(v, u, n);
return u;
}
void dfs5(int u, int fa, i64 d, vector<pair<int, i64>>& a) {
a.emplace_back(u, d);
for (auto [v, w] : e1[u]) if (v != fa && !del[v]) dfs5(v, u, d + w, a);
}
vector<int> ctr;
int rt[N];
vector<pair<int, int>> ege[N];
vector<pair<int, i64>> sub[N];
vector<int> ver[N];
void build(int u) {
dfs3(u, -1); int x = dfs4(u, -1, sz[u]);
ctr.emplace_back(x);
dfs5(x, -1, 0, sub[x]);
vector<int>& s = ver[x];
for (auto [u, d] : sub[x]) s.emplace_back(u);
auto cmp = [&](int x, int y) -> bool {
return dfn[x] < dfn[y];
};
sort(s.begin(), s.end(), cmp); int m = s.size();
for (int i = 1; i < m; i++) s.emplace_back(lca(s[i-1], s[i]));
sort(s.begin(), s.end(), cmp), s.erase(unique(s.begin(), s.end()), s.end());
rt[x] = s[0];
for (int i = 1; i < (int)s.size(); i++) {
int f = lca(s[i-1], s[i]);
ege[x].emplace_back(f, s[i]);
}
del[x] = true;
for (auto [y, w] : e1[x]) if (!del[y]) build(y);
}
void prework() {
iota(fa + 1, fa + n + 1, 1);
dfs1(1, -1), dfs2(1, 0);
for (int i = 1; i <= n; i++) w[i] = a[i] + b[i];
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = cmp(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
build(1);
}
using info = pair<i64, int>; // (w, id)
struct node {
info a, b; int c;
node() : a(inf, -1), b(inf, -1), c(-1) {}
node(int u, i64 w) : a(w, u), b(inf, -1), c(find(u)) {}
} f[N];
node operator+ (const node& x, const node& y) {
node z;
if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
return z;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
node add(node x, int d) {
if (x.a.se != -1) x.a.fi += d;
if (x.b.se != -1) x.b.fi += d;
return x;
}
info out[N];
vector<int> e3[N];
void dfs5(int u) {
for (int v : e3[u]) dfs5(v), f[u] += add(f[v], b[v] - b[u]);
}
void dfs6(int u) {
for (int v : e3[u]) f[v] += add(f[u], b[v] - b[u]), dfs6(v);
}
void _main() {
cin >> n;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e1[u].emplace_back(v, w), e1[v].emplace_back(u, w);
}
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e2[u].emplace_back(v, w), e2[v].emplace_back(u, w);
}
prework();
i64 res = 0;
for (int cnt = 0; cnt < n-1; ) {
fill(out + 1, out + n + 1, info{inf, -1});
for (int x : ctr) {
for (int u : ver[x]) f[u] = node(), e3[u].clear();
for (auto [u, d] : sub[x]) f[u] = node(u, d);
for (auto [u, v] : ege[x]) e3[u].emplace_back(v);
dfs5(rt[x]), dfs6(rt[x]);
for (auto [u, d] : sub[x]) {
node q = add(f[u], d);
chkmin(out[find(u)], q.c == find(u) ? q.b : q.a);
}
}
for (int u = 1; u <= n; u++) {
if (u != find(u) || out[u].se == -1) continue;
if (unite(u, out[u].se)) cnt++, res += out[u].fi;
}
} cout << res;
}
:::::
P4768 [NOI2018] 归程
给定
n 个点m 条边的无向连通图,边有两种权值l_i,a_i 。多测,$T \le 3$,$n \le 2 \times 10^5$,$m,q \le 4 \times 10^5$,4 秒,512 MB。
:::::success[题解]
对于
考虑对
从
只需求出最浅的
| 视 |
|---|
:::::info[代码]
const int N = 4e5 + 5;
using edge3 = tuple<int, int, int>;
i64 n, m, q, op, s;
vector<pair<int, i64>> el[N];
vector<edge3> ea;
i64 dis[N];
struct node {
int v; i64 w;
node(int a = 0, i64 b = 0) : v(a), w(b) {}
bool operator< (const node& a) const {return w > a.w;}
};
void dijkstra(int s) {
memset(dis, 0x3f, sizeof(dis));
priority_queue<node> q;
dis[s] = 0, q.emplace(s, 0);
while (!q.empty()) {
auto [u, d] = q.top(); q.pop();
if (d != dis[u]) continue;
for (auto [v, w] : el[u]) {
if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.emplace(v, dis[v]);
}
}
}
int tot, fa[N], wei[N], f[20][N];
i64 val[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<int> et[N];
void kruskal() {
for (int i = 1; i <= 2 * n; i++) et[i].clear();
iota(fa + 1, fa + 2 * n + 1, 1), tot = n;
sort(ea.begin(), ea.end(), greater<edge3>());
for (auto [w, u, v] : ea) {
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fu] = fa[fv] = ++tot, wei[tot] = w;
et[tot].emplace_back(fu), et[tot].emplace_back(fv);
}
}
void dfs(int u) {
if (et[u].empty()) return val[u] = dis[u], void();
for (int v : et[u]) f[0][v] = u, dfs(v), chkmin(val[u], val[v]);
}
i64 ask(int u, int k) {
for (int i = lg(tot); i >= 0; i--) {
if (f[i][u] && wei[f[i][u]] > k) u = f[i][u];
} return val[u];
}
void _main() {
cin >> n >> m; ea.clear();
for (int i = 1; i <= n; i++) el[i].clear();
for (int i = 1, u, v, l, a; i <= m; i++) {
cin >> u >> v >> l >> a;
el[u].emplace_back(v, l), el[v].emplace_back(u, l);
ea.emplace_back(a, u, v);
}
dijkstra(1), kruskal();
memset(val, 0x3f, sizeof(val)), f[0][tot] = 0, dfs(tot);
for (int i = 1; (1 << i) <= tot; i++)
for (int j = 1; j <= tot; j++) f[i][j] = f[i - 1][f[i - 1][j]];
cin >> q >> op >> s;
for (i64 u, k, last = 0; q--; ) {
cin >> u >> k;
u = (u + op * last - 1) % n + 1;
k = (k + op * last) % (s + 1);
cout << (last = ask(u, k)) << '\n';
}
}
:::::
P6765 [APIO2020] 交换城市
给定
n 个点m 条边的无向带权连通图。$n \le 10^5$,$m,q \le 2 \times 10^5$,1.5 秒,512 MB。
:::::success[题解]
先考虑怎么判定有解。经过思考,我们发现
情况一:环
如图所示,此时
情况二:三度点
如图所示,此时
概括一下,只要
考虑带权并查集,记录
定义
在原本的重构树上,
考虑环的问题如何解决,可以魔改一下 Kruskal 重构树的形态。在 Kruskal 过程中,若
| 在查询时,LCA 上方额外多出一个新点,因此环的情形也能被 |
|---|
:::::info[代码]
const int N = 3e5 + 5;
int n, m, tot, wei[N], deg[N], fa[N], c1[N], c2[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<tuple<int, int, int>> e;
vector<int> et[N];
void upd(int u, int x) {
if (deg[u] == 1) c1[find(u)] += x;
if (deg[u] == 2) c2[find(u)] += x;
}
int h[N], f[N], sz[N], son[N], dep[N], top[N];
void dfs1(int u) {
if (c1[u] == 2 && c1[u] + c2[u] == sz[u]) h[u] = h[f[u]];
else h[u] = u;
sz[u] = 1;
for (int v : et[u]) {
dep[v] = dep[u] + 1, f[v] = u, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int v : et[u]) if (v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = f[top[u]];
} return dep[u] < dep[v] ? u : v;
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
::n = N, ::m = M;
for (int i = 0; i < m; i++) e.emplace_back(W[i], U[i] + 1, V[i] + 1);
sort(e.begin(), e.end());
iota(fa + 1, fa + n + m + 1, 1), fill(sz + 1, sz + n + 1, 1), tot = n;
for (auto [w, u, v] : e) {
int fu = find(u), fv = find(v);
if (fu != fv) {
wei[++tot] = w;
sz[tot] = sz[fu] + sz[fv], c1[tot] = c1[fu] + c1[fv], c2[tot] = c2[fu] + c2[fv];
fa[fu] = fa[fv] = tot;
et[tot].emplace_back(fu), et[tot].emplace_back(fv);
} else if (wei[fu] != w) {
wei[++tot] = w;
sz[tot] = sz[fu], c1[tot] = c1[fu], c2[tot] = c2[fu];
fa[fu] = tot, et[tot].emplace_back(fu);
}
upd(u, -1), upd(v, -1);
deg[u]++, deg[v]++;
upd(u, 1), upd(v, 1);
}
dfs1(tot), dfs2(tot, tot);
}
int getMinimumFuelCapacity(int X, int Y) {
int u = X + 1, v = Y + 1, p = lca(u, v);
return h[p] ? wei[h[p]] : -1;
}
:::::
P13342 [EGOI 2025] Wind Turbines / 风力涡轮机
给定
n 个点m 条边的无向带权图。$n,m \le 10^5$,$q \le 2 \times 10^5$,4 秒,1024 MB。
:::::success[题解]
问题容易描述为:每个询问给出
考虑特殊性质,即
将上述观察扩展到一般情况。记
这里需要说明一点,前
类似 NOIP2024 T4 的结论,可以将所求转化成
考虑节点
可以用 set 配合 dsu on tree 求出所有支配对。详细的求法见这篇题解。
现在问题转化为:有
转
考虑扫描线。固定直线
| 至此问题解决。视 |
|---|
:::::info[代码]
const int N = 2e5 + 5;
int n, m, q, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
struct BIT {
i64 tr[N];
void add(int x, i64 c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
i64 ask(int x) {
i64 res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} T;
vector<tuple<int, int, int>> ed;
int tot, f[N]; i64 mst;
vector<int> e[N];
void kruskal() {
sort(ed.begin(), ed.end()), tot = n;
iota(fa + 1, fa + 2 * n + 1, 1);
for (auto [w, u, v] : ed) {
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fu] = fa[fv] = ++tot, mst += w, f[tot] = w;
e[tot].emplace_back(fu), e[tot].emplace_back(fv);
}
}
using node = pair<int, int>;
set<int> st[N];
vector<node> p[N];
void dfs(int u) {
if (u <= n) return st[u].emplace(u), void();
for (int v : e[u]) {
dfs(v);
if (st[u].size() < st[v].size()) swap(st[u], st[v]);
for (int x : st[v]) {
auto it = st[u].lower_bound(x);
if (it != st[u].end()) p[x].emplace_back(u, *it);
if (it != st[u].begin()) it--, p[*it].emplace_back(u, x);
}
for (int x : st[v]) st[u].emplace(x);
}
}
i64 h[N], ans[N];
vector<node> qry[N];
void _main() {
cin >> n >> m >> q;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w; u++, v++;
ed.emplace_back(w, u, v);
}
kruskal();
for (int i = 1; i <= tot; i++) if (i == fa[i]) dfs(i);
for (int i = 1, l, r; i <= q; i++) {
cin >> l >> r; l++, r++;
qry[l].emplace_back(r, i);
}
fill(h + 1, h + tot + 1, n + 1);
for (int i = n; i >= 1; i--) {
for (auto [x, y] : p[i]) {
if (y >= h[x]) continue;
T.add(h[x], -f[x]);
h[x] = y, T.add(h[x], f[x]);
}
for (auto [j, id] : qry[i]) ans[id] = T.ask(j);
}
for (int i = 1; i <= q; i++) cout << mst - ans[i] << '\n';
}
:::::
CF1797F Li Hua and Path
给定一棵节点数为
n 的无根树。称点对(u,v) 是好的,当且仅当u<v 且下列两个条件恰好有一个为真:
你需要支持
q 次加叶子,保证叶子的标号最大,在操作前和每次操作后求出好点对的数目。
:::::success[题解] 先考虑没询问咋做,并且假定你不会淀粉质。
考虑容斥。记满足第一个条件的点对集合为
先计算
在普通的 Kruskal 重构树中,我们在集合合并时要建一个虚点,形成一棵二叉树。而这里建出的则是关于点权的多叉树,因此这个东西也叫做多叉重构树。
在上述流程建出的树中,
事实上,一条属于集合
在重构树上刻画,则
考虑加叶子怎么处理。此时这个节点
根据容斥公式得到答案
| 复杂度 |
|---|
:::::info[代码]
const int N = 4e5 + 5;
int n, q, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<int> e[N], emx[N], emn[N];
int dn, sz[N], dfn[N], cnt[N], dep[N];
void dfs1(int u) {
sz[u] = 1, dfn[u] = ++dn;
for (int v : emx[u]) dfs1(v), sz[u] += sz[v];
}
void dfs2(int u) {
cnt[u] = 1;
for (int v : emn[u]) dep[v] = dep[u] + 1, dfs2(v), cnt[u] += cnt[v];
}
struct BIT {
i64 tr[N];
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
i64 ask(int x) {
i64 res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
i64 ask(int l, int r) {return ask(r) - ask(l - 1);}
} T;
i64 dfs3(int u) {
i64 res = T.ask(dfn[u], dfn[u] + sz[u] - 1);
T.add(dfn[u], 1);
for (int v : emn[u]) res += dfs3(v);
T.add(dfn[u], -1);
return res;
}
void _main() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
cin >> q; iota(fa + 1, fa + n + 1, 1);
for (int u = 1; u <= n; u++) for (int v : e[u]) {
int fu = find(u), fv = find(v);
if (v < u && fu != fv) emx[u].emplace_back(fv), fa[fv] = fu;
}
iota(fa + 1, fa + n + 1, 1);
for (int u = n; u >= 1; u--) for (int v : e[u]) {
int fu = find(u), fv = find(v);
if (v > u && fu != fv) emn[u].emplace_back(fv), fa[fv] = fu;
}
dfs1(n), dfs2(1);
i64 res = accumulate(sz + 1, sz + n + 1, 0LL);
res += accumulate(cnt + 1, cnt + n + 1, 0LL);
res -= 2 * dfs3(1), res -= 2 * n;
cout << res << '\n';
for (int i = 1, u; i <= q; i++) {
cin >> u, dep[i + n] = dep[u] + 1;
res += n + i - dep[i + n] - 1;
cout << res << '\n';
}
}
:::::
P2619 [国家集训队] Tree I
给定
n 个点m 条边的无向带权连通图,每条边有黑白两色。求恰好有k 条白色边的生成树中,边权和最小的生成树,并输出答案。
:::::success[题解]
我们声称答案关于
考虑 WQS 二分斜率
注意到二分时只要合并黑边和白边两个有序数组,可以归并优化,做到
类似题目是 P5633。两个题的注意事项可以参见讨论区。
:::::
:::::info[代码]
const int N = 1e5 + 5;
int n, m, k, c0, c1, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
struct edge {
int u, v, w, col;
bool operator< (const edge& e) const {
return w != e.w ? w < e.w : col < e.col;
}
} a[N], b[N], c[N];
void _main() {
cin >> n >> m >> k;
for (int i = 1, u, v, w, c; i <= m; i++) {
cin >> u >> v >> w >> c; u++, v++;
if (c == 0) a[++c0] = {u, v, w, c};
else b[++c1] = {u, v, w, c};
}
sort(a + 1, a + c0 + 1), sort(b + 1, b + c1 + 1);
int l = -100, r = 100, res = -1;
while (l <= r) {
int mid = (l + r) >> 1, sum = 0, cnt = 0;
auto check = [&]() -> void {
iota(fa + 1, fa + n + 1, 1);
for (int i = 1; i <= c0; i++) a[i].w += mid;
merge(a + 1, a + c0 + 1, b + 1, b + c1 + 1, c + 1);
for (int i = 1; i <= m; i++) {
int fu = find(c[i].u), fv = find(c[i].v);
if (fu == fv) continue;
fa[fu] = fv, sum += c[i].w;
if (c[i].col == 0) cnt++;
}
for (int i = 1; i <= c0; i++) a[i].w -= mid;
};
check();
if (cnt >= k) l = mid + 1, res = sum - k * mid;
else r = mid - 1;
}
cout << res;
}
:::::
CF1054G New Road Network
现有
n 个点和m 个集合S_i ,构造一棵n 个点的树T ,使得\forall i \in [1,m], S_i 的导出子图连通。输出构造或报告无解。多测,
\sum n, \sum m \le 2 \times 10^3 ,2 秒,250 MB。
:::::success[题解]
对集合
设所有
另一方面,记
取完全图
:::::
:::::info[代码]
const int N = 2005;
int n, m, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
char s[N];
bitset<N> a[N];
struct edge {
int u, v, w;
bool operator< (const edge& o) const {return w > o.w;}
} e[N*N];
void _main() {
cin >> n >> m; iota(fa + 1, fa + n + 1, 1);
for (int u = 1; u <= n; u++) a[u].reset();
int sum = 0, mst = 0;
for (int i = 1; i <= m; i++) {
cin >> (s + 1);
for (int u = 1; u <= n; u++) if (s[u] == '1') a[u][i] = 1;
sum += count(s + 1, s + n + 1, '1') - 1;
}
int tot = 0;
for (int u = 1; u <= n; u++) for (int v = 1; v < u; v++)
e[++tot] = {u, v, (a[u] & a[v]).count()};
sort(e + 1, e + tot + 1);
vector<edge> T;
for (int i = 1; i <= tot; i++) {
int u = find(e[i].u), v = find(e[i].v), w = e[i].w;
if (u == v) continue;
fa[u] = v, mst += w, T.emplace_back(e[i]);
}
if (mst != sum) return cout << "NO\n", void();
cout << "YES\n";
for (auto [u, v, w] : T) cout << u << ' ' << v << '\n';
}
:::::