答案等于所有使「只留权值能被 d 整除的边后图连通」的 d 的最小公倍数,枚举 d 用并查集判连通即可。
OJ: roj
题目 ID: 1713
难度:提高+/省选-
标签:图论并查集数论生成树python
创建: 2026-10-07 17:50
更新: 2026-10-07 17:50
形式化题目
给定一张
要求输出
数据范围:
以样例为例,
| 生成树 | 边权集合 | |
|---|---|---|
| 去掉 |
||
| 去掉 |
||
| 去掉 |
正解
思路
从"枚举生成树"改成"枚举因子"。 生成树数量是指数级的,但
定义
则
核心结论。
证明。 记
- 任取生成树
,令 。由 的定义 对 的每条边成立, 所以 的每条边都留在 里, 是 的生成树, 连通,即 。 于是 。这对每棵 都成立,故 。 - 任取
。 连通,取它的一棵生成树 ,则 对 的每条边 成立,故 。对所有 取 得 。
两向合并即
这个结论的直觉是:
怎么判定 comp(初值 comp == 1。
复杂度怎么压。 朴素地对每个 cnt[w] / st[w] 记录"权值
其中
答案用无符号 64 位。 题面保证 unsigned long long,
输出格式串是 %llu。另一个细节:按 ans / gcd(ans, d) * d 不会中途溢出。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 17:50
# update_at: 2026-10-07 17:50
import sys
from math import lcm
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Buckets = dict[int, list[tuple[int, int]]] # 边权 -> 该权值的边表 [(u, v)]
def find(parent: list[int], x: int) -> int:
"""并查集找根:路径减半,顺路把 x 直挂祖父。"""
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def spans(n: int, buckets: Buckets, d: int, maxw: int) -> bool:
"""只保留边权为 d 的倍数的边(记作 G_d)后,整张图是否连通。"""
parent = list(range(n + 1))
comp = n # 当前连通块个数
for k in range(d, maxw + 1, d):
edges = buckets.get(k)
if edges is None:
continue
for u, v in edges:
ru, rv = find(parent, u), find(parent, v)
if ru != rv:
parent[rv] = ru
comp -= 1
if comp == 1: # 已经连通,后面那些桶不必再看
return True
return comp == 1
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
buckets: Buckets = {}
for _ in range(m):
u, v, w = next(data), next(data), next(data)
buckets.setdefault(w, []).append((u, v))
# n = 1(必然 m = 0)只有唯一的空生成树,约定答案为 1
if n <= 1 or not buckets:
print(1)
return
maxw = max(buckets) # d 只需枚举到最大边权,更大的 d 一条可用边都没有
weight_count = {w: len(edges) for w, edges in buckets.items()} # 每个权值有几条边
# avail[d] = 边权能被 d 整除的边数(下标 0 占位不用);不足 n-1 条时 G_d 必然不连通,
# 这种 d 连并查集都不用建,先用 O(w log w) 的调和级数前缀把它筛掉
avail = [0] + [sum(weight_count.get(k, 0) for k in range(d, maxw + 1, d))
for d in range(1, maxw + 1)]
ans = 1
for d in range(1, maxw + 1):
enough_edges = avail[d] >= n - 1
if enough_edges and spans(n, buckets, d, maxw):
ans = lcm(ans, d) # G_d 连通 ⇔ d 整除某棵生成树的边权 gcd
print(ans)
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 17:50
* update_at: 2026-10-07 17:50
*/
// 1713 生成树:所有生成树的"边权 gcd"的 lcm。
//
// 关键结论:记 D = { d >= 1 : 只保留权值能被 d 整除的边后图连通 },则答案 = lcm(D)。
// 任取生成树 T,g = gcd(T) 整除 T 的每条边,故 T 全部落在 G_g 里,G_g 连通,g ∈ D;
// 反过来 d ∈ D 时取 G_d 的生成树 T,有 d | gcd(T)。两边取 lcm 即得相等。
// 于是只需对 d = 1..maxW 判一次连通性,连通就 ans = lcm(ans, d)。
//
// 复杂度:每个 d 重置一次并查集 O(N),共 O(N * maxW);并查集合并次数为 Σ_e τ(w_e)
// (τ 为约数个数,1e5 条边 × 平均约 10 个约数)。N <= 1000、maxW <= 32767 时约 4e7 次
// 基本操作,1s 内安全。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; // 答案上界为 2^64-1(样例 9 已超过 2^63-1),必须无符号
const int MAXN = 1005;
const int MAXM = 100005;
const int MAXW = 32770; // 2^15 - 1 = 32767,权值桶数组开大一点
struct Edge {
int u, v, w;
};
int n, m;
Edge e[MAXM]; // 全部边,按权值升序排序后存放
int cnt[MAXW]; // cnt[w] = 权值恰为 w 的边数
int st[MAXW]; // 权值 w 的边在排序后数组中的起始下标
int par[MAXN]; // 并查集:父指针
int sz[MAXN]; // 并查集:按大小合并用的集合大小
void dsu_init() {
for (int i = 1; i <= n; ++i) {
par[i] = i;
sz[i] = 1;
}
}
int find_root(int x) {
while (par[x] != x) {
par[x] = par[par[x]]; // 路径减半
x = par[x];
}
return x;
}
// 合并两个集合,返回是否真的合并(即是否减少了一个连通块)
bool unite(int a, int b) {
a = find_root(a);
b = find_root(b);
if (a == b) return false;
if (sz[a] < sz[b]) {
int t = a;
a = b;
b = t;
}
par[b] = a;
sz[a] += sz[b];
return true;
}
ull gcd_ull(ull a, ull b) {
while (b) {
ull t = a % b;
a = b;
b = t;
}
return a;
}
// 每个中间 lcm 都整除最终答案,所以 a / gcd(a, b) * b 不会中途溢出
ull lcm_ull(ull a, ull b) {
return a / gcd_ull(a, b) * b;
}
bool cmp_w(const Edge& a, const Edge& b) {
return a.w < b.w;
}
int main() {
scanf("%d %d", &n, &m);
int maxW = 0;
for (int i = 0; i < m; ++i) {
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
++cnt[e[i].w];
if (e[i].w > maxW) maxW = e[i].w;
}
// n = 1(此时必然 m = 0)只有唯一的空生成树,约定答案为 1
if (n <= 1 || maxW == 0) {
printf("1\n");
return 0;
}
// 按权值分桶:排序后 cnt/st 即可把"权值为 k 的边"定位成一段连续区间
sort(e, e + m, cmp_w);
st[0] = 0;
for (int w = 0; w < maxW; ++w) {
st[w + 1] = st[w] + cnt[w];
}
ull ans = 1;
for (int d = 1; d <= maxW; ++d) {
// d 的倍数里一条边都没有时 G_d 必不连通,先跳过,省掉一次并查集重置
bool any = false;
for (int k = d; k <= maxW; k += d) {
if (cnt[k]) {
any = true;
break;
}
}
if (!any) continue;
dsu_init();
int comp = n; // 当前连通块个数
for (int k = d; k <= maxW && comp > 1; k += d) {
for (int i = st[k]; i < st[k] + cnt[k]; ++i) {
if (unite(e[i].u, e[i].v)) --comp;
}
}
if (comp == 1) ans = lcm_ull(ans, (ull)d); // G_d 连通 ⇔ d ∈ D
}
printf("%llu\n", ans);
return 0;
}复杂度
- 时间:并查集重置
次共 ;并查集合并次数为 ,每次均摊 ;再加上筛"该 有没有边" 的 调和级数代价。总计约 次基本操作, 实测最大数据点( 、 )在 1 s 限时内安全。 - 空间:边表
,分桶数组 ,并查集 ,共 。
Python 版同一算法:主循环仍是枚举 avail[d](
总结
本题是"
- 换视角:不枚举指数级的生成树,而是枚举
,把" 使 " 等价成" 连通",得到一个 项的集合 ; - 取对偶:
, 两边分别由" "和" "给出,都是整除链上的直接结论。
实现上真正省时间的是按权值分桶:把
关于本题素材的两点说明(如实注明):
- 本题的测试数据由素材源里的
data.py用 cyaron 自造(分层生成:、 、边权全为 的幂、以及两组大随机),题面则来自《信息学奥赛一本通 · 高手训练篇》的重建,因此数据未必覆盖官方原题的全部强度,本页结论以题面与 本地数据为准。 - 素材源的
std.cpp与题面一致(同一套算法),已编译跑通全部 10 个数据点并与.out逐点比对通过;另用"枚举全部生成树求"的暴力解在 的小图上 固定种子对拍通过,故本页按题面自研的实现与素材源结论一致,未发现 std 与题面不符的情况。