无线广播问题与二分图判定：BFS染色算法详解

PA7题解报告——无线广播(Broadcast)这道题我前前后后做了三遍。第一遍用邻接矩阵硬开第二遍学会了链式前向星但没处理非连通图第三遍才真正把二分图染色的思路吃透。如果你正在被这道题卡住或者做完之后总觉得哪里似懂非懂那这篇题解应该能帮你把这层窗户纸捅破。先说结论PA7无线广播本质上是一个二分图判定问题考的是建图能力加BFS/DFS染色基本功。题目本身不长但坑很多尤其是建图的条件判断、浮点数精度、以及图不连通时的处理方式稍不留神就能WA到怀疑人生。下面我从建模开始一步步把整个题拆开讲透。1. 问题是什么以及它到底在考什么题目大意是这样某地区有若干个广播站每个广播站有一个坐标通常是三维坐标但二维也常见还有一个广播半径。两个广播站如果距离不超过某个阈值一般是两倍半径也就是2R就认为会产生干扰不能分配相同的频率。现在只有两个频率可用A和B问是否存在一种分配方案让所有广播站都正常工作。翻译成人话就是每个广播站是图上的一个点两个不能同频率的广播站之间连一条边然后判断这张图能不能用两种颜色给所有点染色使得相邻点颜色不同。能。这就是二分图判定。有冲突就是不能没有冲突就是能。这道题在考什么我拆出三个点建模能力能不能把广播站干扰关系快速转化为点边的图论模型。这一步做不好后面全是空中楼阁。算法基础二分图判定的标准做法是DFS或BFS染色。你需要知道为什么染色能判定二分图以及复杂度是多少。工程细节浮点比较、数组空间、非连通图、多组数据初始化——这些才是真正拉开差距的地方。第三点最容易被忽视。我见过不少同学算法思路完全正确但代码写出来就是过不了最后发现是在距离判断时直接用了浮点数相等比较或者没有处理多组测试用例的数据残留。这些坑后面我逐个说。2. 从广播站到图建图细节与边界讨论2.1 干扰关系的判定条件这个环节的核心就是一条公式两个广播站i和j之间需要连边当且仅当它们之间的距离dist(i, j) 2 * R。注意这里的R是广播半径。为什么是2R不是R因为广播是双向的两个站的覆盖范围各自延展R如果两个圆心之间的距离小于等于两个半径之和那么它们的覆盖区域就会重叠重叠区域的设备会同时收到两个信号产生同频干扰。具体到计算dist(i, j) sqrt((x_i - x_j)^2 (y_i - y_j)^2 (z_i - z_j)^2)然后判断dist(i, j) 2 * R是否成立。这里有一个重要优化比较距离时不一定要开根号。因为平方函数在正数区间上是单调递增的所以可以直接比较距离平方和(2R)^2dx x_i - x_j dy y_i - y_j dz z_i - z_j d2 dx*dx dy*dy dz*dz if (d2 4 * R * R) // 使用整数或double比较这样做的好处有两个。第一省去sqrt运算在大规模点集比如5000个点下能明显减少计算量第二避免了一次浮点误差的引入。但这里有个细节如果坐标和半径都是整数用整数类型的平方判等是完全没问题的。如果坐标是浮点数建议在比较时加一个极小量 epsilon比如d2 4 * R * R 1e-9以免出现边界情况被误差卡掉。这是我在实测中踩过的坑后面调试实录里细说。2.2 邻接表的构建策略确定好连边条件后下一步就是建图。常见的方式有三种建图方式适用场景优点缺点邻接矩阵 E[i][j]n 500写起来简单O(n^2)空间容易爆vector邻接表n 10^5实现方便动态扩容速度略慢内存碎片链式前向星 head/next/ton 10^6内存紧凑速度快写法稍绕易错对于PA7这种数据规模一般来说n不会超过几万vector邻接表是性价比最高的选择。我第一版代码用邻接矩阵开到[10005][10005]的 bool 数组编译过了运行直接MLE后来改成 vector 才过。另外还有一个选择不建图直接在染色时对每个点遍历其他点判断是否干扰再递归染色。这种方法叫隐式图遍历空间省了但时间变成O(n^2)倍递归。只适合n很小的情况比如n 200。如果n超过1000强烈建议老老实实建邻接表否则每次BFS都要把所有点对重新算一遍距离白白浪费大量时间。3. 核心解法BFS染色判二分图3.1 为什么二分图恰好对应这个问题的解你现在有n个广播站只有A、B两个频率。如果把频率A看成颜色0频率B看成颜色1那么相邻点不能同色这个约束就完全等价于给图的每个顶点染色使得每条边的两个端点颜色不同。满足这个条件的图就叫二分图。反过来如果一张图是二分图那它一定存在一个合法的二染色方案也就是这道题的合法频率分配方案。所以问题从能不能分配频率变成了这张图是不是二分图。数学上有一个重要结论一张无向图是二分图当且仅当它不包含奇环。也就是说如果图中存在一个长度为奇数的环那这个图一定不是二分图否则就是。这个结论很好理解。想象一个三角形长度为3的环三个点两两相邻你用两个颜色去染第一个点染A第二个点必须染B但第三个点同时连着一和二无论染A还是B都会和其中一个冲突。所以三角形不可能被二染色。长度5、7、9的环同理奇数环都会导致矛盾。那么怎么判断图中是否存在奇环最实用的方法就是染色法从一个点出发给它染上颜色0然后它相邻的点全部染颜色1这些点的相邻点再染颜色0……如果某个点在染色过程中被发现已经被染过而且颜色和当前要求的颜色不一致那就说明存在矛盾也说明图中存在奇环判定为不是二分图。3.2 BFS染色实现细节染色有两种写法DFS和BFS。我建议用BFS。为什么因为DFS在竞赛中虽然代码短但递归深度可能达到n一旦n达到10万系统栈就会溢出。BFS用队列完全没有栈溢出的问题。而且这道题的图很可能是稀疏图BFS遍历所有点和边的时间就是O(n m)非常稳定。BFS染色的核心逻辑1. 初始化 color 数组为 -1表示未访问 2. 对每个点 i - 如果 color[i] ! -1说明已经在一个连通块中被染过跳过 - 否则从 i 开始BFS a. color[i] 0 b. i入队 c. 队列非空时 - 取出队首 u - 遍历 u 的所有邻居 v - 如果 color[v] -1则 color[v] 1 - color[u]v入队 - 如果 color[v] color[u]说明冲突直接输出失败 3. 所有点都遍历完且没有冲突输出成功这个逻辑里最重要的一点是外层循环要遍历所有点。因为图不一定连通——有的广播站互相够不着会形成多个独立的连通分量。每个连通分量都要单独染色。所以外层for i 1 to n不能省。你可以想象成把一个班级分成了好几个完全不相干的小组每个小组单独安排值日互不影响。任何一个小组安排不了整个方案就失败。3.3 复杂度分析建图阶段需要遍历所有点对判断是否需要连边复杂度 O(n^2)。n 5000 时有1250万次距离计算是可以接受的。染色阶段BFS遍历所有点和边。若图为稀疏图复杂度 O(n m)最坏情况下完全图m n(n-1)/2复杂度 O(n^2)。所以整道题的瓶颈通常在建图。如果n开到1e5O(n^2)建图就会超时这时候需要考虑空间索引如 KD-Tree 或网格划分来优化但这属于进阶玩法PA7不太会考到那么极限的数据规模。4. 完整题解代码与逐行拆解下面给出一个我个人比较满意的标准写法采用 vector 邻接表 BFS 染色。注释写得很细可以直接照着敲。#include bits/stdc.h using namespace std; const int MAXN 5005; // 根据题目数据范围调整 const double eps 1e-9; // 浮点误差修正 struct Station { double x, y, z; double r; } st[MAXN]; vectorint G[MAXN]; // 邻接表 int color[MAXN]; // 染色数组-1表示未染 // 判断两个广播站是否干扰 bool conflict(int i, int j) { double dx st[i].x - st[j].x; double dy st[i].y - st[j].y; double dz st[i].z - st[j].z; double d2 dx*dx dy*dy dz*dz; double limit st[i].r st[j].r; // 干扰距离阈值 return d2 limit * limit eps; } // 从start点出发做BFS染色返回true表示这个连通分量合法 bool bfs(int start) { queueint q; color[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : G[u]) { if (color[v] -1) { color[v] 1 - color[u]; // 邻居染相反颜色 q.push(v); } else if (color[v] color[u]) { return false; // 冲突不是二分图 } } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { cin st[i].x st[i].y st[i].z st[i].r; } // 建图O(n^2)判断所有点对是否干扰 for (int i 0; i n; i) { for (int j i1; j n; j) { if (conflict(i, j)) { G[i].push_back(j); G[j].push_back(i); } } } // 初始化染色数组 memset(color, -1, sizeof(color)); // 遍历所有连通分量 bool ok true; for (int i 0; i n; i) { if (color[i] -1) { if (!bfs(i)) { ok false; break; } } } cout (ok ? YES : NO) endl; return 0; }4.1 数据结构与输入处理结构体Station存放坐标和半径。注意如果题目的坐标给出的是整数你完全可以用 int 类型来存然后距离平方用 long long 来算以免dx*dx溢出 int 范围。这是经典溢出坑三维坐标如果到1e4平方之后就是1e8三个加起来3e8还在int范围但如果坐标上到1e5那平方就是1e10int直接爆。稳妥起见用 double 或者 long long。输入用cin没问题但记得加上两行ios::sync_with_stdio(false); cin.tie(nullptr);不加这两行数据量大时 scanf 和 cin 混用或者 cin 默认绑定都会拖慢速度。刷题老手都懂这个操作。4.2 键级细节conflict函数中的阈值我在这里选择用limit st[i].r st[j].r而不是2 * R。为什么因为如果题目描述是每个广播站的覆盖半径为R任意两站距离小于等于R1R2会互相干扰那点对之间的阈值应当是两个半径之和。有的题目里所有站半径相同那自然就是2R。但有的题目可能会给每个站不同的功率和覆盖半径这样就必须逐对计算阈值。我建议写成通用版本也就是limit r1 r2。这样不管题目是不是统一半径代码都不用改。工程上这叫把可变因素参数化竞赛中也是好习惯。比较时加上 eps是一个保险动作。比如理论边界值刚好等于 limit但浮点计算得到0.9999999999你拿它去和limit * limit比较就会误判为不干扰从而漏掉一条关键边。加上 eps 之后哪怕有极小的浮点误差也能正确判定边界情况。4.3 BFS染色中的关键判断冲突判断就一句color[v] color[u]。意思是邻居 v 已经染过色而且和当前点 u 同色说明这条边的两个端点在当前方案中频率相同不可行。这里有个容易误解的点为什么 color[v] 不等于 color[u] 就一定是合法的因为如果 v 已经染过色且颜色与 u 相反说明 v 在之前从另一个路径被访问到了并且它被正确地赋了一个与 u 相反的颜色那这条边是满足约束的不需要再处理。而如果 v 没有被访问过color[v] -1就给它染上1 - color[u]然后入队。你可能会问为什么一定只有 -1 才入队如果 v 已经被染过且颜色合法则这条边已经处理过了不需要重复入队。BFS 中一个点只入队一次时间复杂度才稳定在 O(nm)。5. 常见错误与调试实录5.1 浮点精度导致漏边第一次做这道题时我写的是if (sqrt(d2) 2 * R) { ... }用 double 类型看起来没有任何问题。但有一组数据在边界上某个点的距离计算出来是1.9999998而2 * R 2.0小于 2.0 所以应该连边但我的 sqrt 加上浮点误差得到的是2.0000001被判定为不连边答案就错了。后来我把所有距离判断改成平方比较并加上1e-9的 eps这个坑就再也没踩过。经验总结浮点数比较永远是小于等于某个阈值加 epsilon尤其是数据刻意卡边界时差一点就是 WA 和 AC 的区别。5.2 图不连通导致漏判这道题还有一个隐蔽的坑广播站分布很散可能形成多个互不相干的连通分量。如果你只从第一个点开始 BFS完全没检查第2个、第3个点是否已经被访问过那么后面的连通分量里如果有冲突你根本发现不了。我有个同学就是这么写的bfs(0);然后测试数据正好第一个连通块合法后面的块有冲突答案输出 YESWA 了一下午。后来我提醒他要遍历所有未被染色的点他才发现问题。经验总结凡是要对整张图做性质判断的算法都要刻意问自己一句这张图连通吗如果不连通我是不是遗漏了某些分量5.3 数组越界与初始化残留vector 邻接表虽然好用但也要注意每次测试用例之间的清空。如果题目有多组输入你需要for (int i 0; i n; i) { G[i].clear(); } memset(color, -1, sizeof(color) * n); // 或直接对color用vector, assign(n, -1)如果你用固定数组color[MAXN]只memset(color, -1, sizeof(color))全部 m emset 是可以的但要注意 MAXN 是否足够大。我曾经开到MAXN 1005而数据 n 1000第1000个点对应的下标是999刚好没越界但邻接表存边时G[999].push_back(...)却有可能访问到head[1000]的野下标。这类问题很难肉眼发现建议直接把数组开大到两倍或者三倍省心。5.4 边数估算与MLE这道题 n 不大但如果 n 20000完全图边数约2e8条vector 存边的内存会非常恐怖。链式前向星的 int 数组同样需要两条边记录每条边的 to 和 next 各4字节200M条边就要1600MB直接爆。所以遇到大数据光想能不能建图不够还要算内存。题目的交互模式一般不会让 n 大到不可建图但如果真遇到了可以考虑用边查询替代建图的隐式图方案。我在某次模拟赛中把手写的链式前向星封装成模板反而因为多组数据忘了重置cnt而 WA 了两次。从那以后我对固定数组 计数器的模板都特别谨慎每次输出答案前检查一遍计数器的重置逻辑。6. 模板化总结与举一反三这道题做完之后值得把二分图判定模板沉淀下来因为你以后会遇到非常多它的变种比如网格图黑白染色棋盘、地图、炸弹人等问题往往直接就是一个二分图。任务分配问题某些资源冲突、时间冲突场景本质上也是二分图判定只是节点含义变成了任务。双色信号/双屏显示给若干冲突对象分配两个非此即彼的状态一模一样。最大匹配前置很多匹配类算法需要先判定图是二分图才能用匈牙利算法所以这个判定代码本身就是配套组件。我的建议是把 BFS 染色写成不依赖具体题目的通用函数bool isBipartite(const vectorvectorint G, int n) { vectorint color(n, -1); queueint q; for (int i 0; i n; i) { if (color[i] ! -1) continue; color[i] 0; q.push(i); while (!q.empty()) { int u q.front(); q.pop(); for (int v : G[u]) { if (color[v] -1) { color[v] color[u] ^ 1; q.push(v); } else if (color[v] color[u]) { return false; } } } } return true; }注意我用的是color[u] ^ 1而不是1 - color[u]两者等价但位运算在视觉效果上更简洁。整个模块三分钟能敲完每次遇到能不能用两种状态避免冲突类问题直接拉出来用。建图部分则要根据题目灵活调整——PA7是 判断距离是否干扰别的题可能是判断两个区间是否有交集也可能是判断两个字符串是否冲突但核心都是哪些节点不能同色这一条线。最后分享一个我个人的习惯哪怕这道题已经 AC 了我也会再手动构造一些边界测试数据来验证代码。比如只有一个广播站显然应该输出 YES。两个广播站距离刚好等于阈值应该连边并输出 YES因为两个站可以分别用两个频率。三个广播站两两互相干扰构成三角形应该输出 NO。四个广播站构成一个正方形的四条边应该输出 YES。一个链状图长度任意永远都是 YES。用这些边界用例跑一遍基本能保证代码在各种极端情况下都不翻车。这个问题虽然看起来简单但它是图论里模型转化这一基本功的绝佳练习——你从广播站想得到图从图想得到二分图从二分图想得到 BFS 染色每一步都是经验积累。把这条路走通一遍后面遇到更复杂的图论题你会明显感觉自己上手更快了。