全频带阻塞干扰 题解

songyuteng · 2025-11-29 11:23:35 · 题解

全频带阻塞干扰 题解

题目大意

给定一个无向图，每条边有多个可用频带。干扰模式按周期 T 循环，每个时刻会阻塞特定的频带集合。定义两个节点在时刻 t 可通信，当且仅当存在一条路径，路径上每条边至少有一个频带在当前时刻未被阻塞。

需要处理 q 个查询，每个查询问在时刻 t，节点 u 和 v 是否可通信。

思路

观察

如果，你是一个热爱观察的好学生，那么你应该可以发现：

• 频带数量 k 很小（k \leq 10），这意味着我们可以使用状态压缩来表示频带集合。

• 阻塞模式有限，虽然周期 T 可达 1000，但不同的阻塞模式最多只有 2^k = 1024 种。

• 对于相同的阻塞模式，图的连通性是相同的。

构建

为了卡卡时间，这里，我们用一些特殊技巧。

我们可以将每个时刻的阻塞集合和每条边的频带集合用位掩码表示。

::::info[位掩码] 每条边有多个可用频带，我们用位掩码表示：

::::