专栏文章

全频带阻塞干扰 题解

ssongyuteng
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0br4t
此快照首次捕获于
2025/12/01 18:29
3 个月前
此快照最后确认于
2025/12/01 18:29
3 个月前
查看原文

全频带阻塞干扰 题解

题目大意

给定一个无向图，每条边有多个可用频带。干扰模式按周期 TT 循环，每个时刻会阻塞特定的频带集合。定义两个节点在时刻 tt 可通信，当且仅当存在一条路径，路径上每条边至少有一个频带在当前时刻未被阻塞。
需要处理 qq 个查询，每个查询问在时刻 tt，节点 uu 和 vv 是否可通信。

思路

观察

如果，你是一个热爱观察的好学生，那么你应该可以发现：
  • 频带数量 kk 很小（k≤10k \leq 10），这意味着我们可以使用状态压缩来表示频带集合。
  • 阻塞模式有限，虽然周期 TT 可达 10001000，但不同的阻塞模式最多只有 2k=10242^k = 1024 种。
  • 对于相同的阻塞模式，图的连通性是相同的。

构建

为了卡卡时间，这里，我们用一些特殊技巧。
我们可以将每个时刻的阻塞集合和每条边的频带集合用位掩码表示。
位掩码
每条边有多个可用频带，我们用位掩码表示：

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...