1 条题解
-
0
题目分析
情(friendship)题解
题意抽象出来就是:给定一张 个点 条边的无向连通图, 次询问 中有多少整数 满足存在一条从点 到点 的长度为 的路径。保证边权只有 两种。
首先来考虑如果只有边权为 的边怎么做,其实就是经典的奇偶最短路,可以参考 [CSP-J2019] 加工零件。对于每个 先求出 到 的长度为偶数的最短路 和长度为奇数的最短路 ,那么通过在 权边上左右横跳我们就能够构造出所有长度为 和 的路径( 为自然数),又因为不可能有路径的长度比这两个值更小,所以这实际上就是所有可能的路径长度。
注意到这个做法的关键在于抓住一条 权边左右横跳,使得所有比 大的偶数都能被得出(奇数同理)。那对于有 权边的情况,奇最短路经过的边里肯定有 权边,所以不会受到影响;但是偶最短路却有可能仅由 权边组成,此时”左右横跳“的调整就只能做到 而非 ,会漏掉一部分偶数。为了应对这种情况,我们只需要额外求出至少经过一条 权边的偶最短路,这个也是好做的,类似最短路拓展到奇偶最短路,在跑奇偶最短路时额外记录一维 表示目前有没有走过 权边即可。这一部分的复杂度视最短路的实现而定,如果用堆优化 Dijkstra 复杂度为 (默认 同阶)。 回答询问时,奇数部分是一个公差为 的等差数列,偶数部分是公差分别为 的两个等差数列求并,可以通过简单的分类讨论以 的复杂度完成。
- 1
信息
- ID
- 180
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者