NOIP2024集训Day47 生成树+二分图

NOIP2024集训Day47 生成树+二分图

B. [THUPC2022 初赛] 最小公倍树

直接建边显然不行，考虑优化建边。

对于两个点 \(u, v\)，\((u, v)\) 的边权为 \(\displaystyle\operatorname{lcm}(u, v) = \frac{u\times v}{\gcd(u, v)}\)，显然应该选择 \(\gcd(u, v)\) 尽可能大的点对连边，也就是说 \(u, v\) 的公因子越多越好。

由于 \(L,R\le 10^6\)，可以考虑枚举这个公因子。对于因子 \(x\)，如果 \(kx\) 在 \([L, R]\) 中，则 \((k + 1)x\)，\((k + 2)x\)，\(\dots\)，这些点向 \(kx\) 连边是比较优的。所以我们可以找到这个最小的 \(kx\) 作为起点连边。最后跑 Kruskal 即可。

这个建边的套路要记住。

H. [BZOJ4808] 马

首先将棋盘 \(01\) 间隔染色，然后就成了二分图

由于要放最多的马，其实就是最大独立集（最大独立集 = 点数 - 最小点覆盖 = 点数 - 最大匹配）。