1. 项目概述与核心需求解析最近在带学生备赛信奥刷题是绕不开的环节。今天拆解的这道题是CCPC 2023年北京市赛的P10043题标题叫“广播”。乍一看题目名可能会联想到网络通信或者图论里的广播算法但实际接触后发现这是一道非常典型的、考察选手对问题本质抽象能力和算法选择能力的题目。它不像一些纯模板题那样直接套用Dijkstra或BFS就能解决而是需要你从“广播”这个生活场景中提炼出数学模型并选择最高效的算法策略。对于正在从语法学习过渡到算法思维训练的同学来说这类题目是绝佳的磨刀石。这道题的核心场景可以这样理解在一个区域内有若干个信号塔广播站每个塔有一个特定的信号覆盖半径。当一个塔被“激活”广播时其信号范围内的其他塔也会被“唤醒”并开始广播从而产生连锁反应。题目最终要我们判断如果只允许手动激活点燃一个初始信号塔能否通过这种连锁反应最终让所有信号塔都进入广播状态。这本质上是一个图的连通性问题但加上了“覆盖半径”这个几何约束使得建图的过程成为解题的第一个关键点。用C实现它不仅要求熟练掌握STL容器如vector,pair、循环和条件判断更要求能灵活运用深度优先搜索DFS或广度优先搜索BFS来遍历我们构建的“关系图”。2. 问题建模与算法选型思路面对“广播”这道题我们首先要做的不是急着写代码而是把文字描述转化为清晰的数学模型。这是解决所有算法问题的第一步也是最关键的一步。2.1 从物理场景到数学模型题目给出了每个信号塔的坐标 (x, y) 和其广播半径 r。两个塔A和B之间能否触发连锁反应取决于它们之间的距离是否小于等于发起广播的塔的半径。注意这个细节是判断A到B的距离是否小于等于A的半径而不是任意一方的半径。这意味着关系是有向的。如果A能覆盖到B我们就建立一条从A指向B的有向边表示“激活A可以导致B被激活”。因此我们可以将N个信号塔看作N个顶点。遍历每一对顶点i和ji ! j计算它们之间的欧几里得距离dist sqrt((xi-xj)^2 (yi-yj)^2)。如果dist riri是塔i的半径那么就在图中添加一条从i指向j的有向边。这样我们就得到了一个N个顶点、最多N*(N-1)条边的有向图。2.2 算法核心图的遍历建图完成后问题就转化为在这个有向图中是否存在一个顶点源点从它出发进行遍历可以访问到图中的所有其他顶点这正是图的单源可达性问题。对于这类问题我们有两种经典的遍历算法选择深度优先搜索DFS和广度优先搜索BFS。在这个场景下两者都是可行的因为我们要找的是是否存在一条路径而不是最短路径。DFS的实现通常更简洁递归写法一目了然而BFS的迭代写法可能对栈深度更友好尽管本题N≤1000递归深度一般没问题。我个人的习惯是使用DFS因为代码写起来快逻辑清晰。选择哪种取决于你的熟悉程度性能上差异不大。2.3 为什么不是并查集有同学可能会想到并查集Union-Find。并查集擅长处理无向图的连通分量问题。但本题中边是有向的A能覆盖B不代表B能覆盖A因此从A出发能到B并不能将A和B简单地“合并”到同一个集合。并查集在这里不适用它无法表达这种单向的可达关系。我们必须老老实实地对每个可能的起点进行一次全图的遍历检查。算法思路小结输入读取N以及每个塔的x, y, r。建图使用vectorvectorint graph(N)存储邻接表。双重循环判断每对塔如果满足覆盖条件则graph[i].push_back(j)。枚举起点从0到N-1依次将每个塔作为初始激活点。遍历检查从当前起点出发进行DFS或BFS用一个visited数组记录能到达的所有塔。判断结果如果某次遍历后visited数组中所有元素都为true则说明该起点是可行的输出其编号注意题目要求输出编号通常从1开始而我们存储从0开始需要1。如果所有起点都不行则输出-1。优化剪枝一旦找到可行起点立即输出并结束程序即可。3. 核心代码实现与细节剖析接下来我们进入具体的C实现环节。我会将代码分成几个模块并逐一解释关键细节和易错点。3.1 数据结构定义与输入处理首先我们需要存储每个塔的信息。使用结构体struct是最清晰的方式。#include iostream #include vector #include cmath #include cstring // 用于memset using namespace std; struct Tower { int x, y, r; }; int main() { int N; cin N; vectorTower towers(N); for (int i 0; i N; i) { cin towers[i].x towers[i].y towers[i].r; } // ... 后续代码 }这里有一个注意事项坐标和半径的取值范围题目未明确给出但计算距离时涉及平方操作int类型可能溢出。稳妥起见可以使用long long来存储计算过程中的平方值。或者在本题N≤1000且坐标半径值不会太大的竞赛环境下int通常可以接受但养成考虑数据范围的习惯很重要。3.2 建图邻接表的构建建图是性能的关键。使用邻接表比邻接矩阵更节省空间稀疏图。// 继续main函数 vectorvectorint graph(N); // 邻接表graph[i]存储从塔i能直接覆盖的塔的编号 for (int i 0; i N; i) { for (int j 0; j N; j) { if (i j) continue; // 自己到自己不需要判断 long long dx towers[i].x - towers[j].x; long long dy towers[i].y - towers[j].y; long long dist_sq dx * dx dy * dy; // 距离的平方 long long r_sq (long long)towers[i].r * towers[i].r; // 半径的平方 // 比较距离平方和半径平方避免使用sqrt提高效率与精度 if (dist_sq r_sq) { graph[i].push_back(j); } } }关键技巧避免使用sqrt。sqrt函数计算开方较慢且可能引入浮点数精度误差。我们直接比较距离的平方和半径的平方这在数学上是等价的但效率更高且完全避免了精度问题。这是竞赛中处理距离判断的常用优化手段。3.3 深度优先搜索DFS的实现接下来实现DFS遍历函数。我们需要一个visited数组来记录哪些塔已被访问。// 全局或通过引用传递的visited数组 vectorbool visited; void dfs(int u, const vectorvectorint g) { visited[u] true; for (int v : g[u]) { // 遍历当前塔u能覆盖的所有塔v if (!visited[v]) { dfs(v, g); } } }这个DFS函数非常标准。参数u是当前访问的节点塔g是图的邻接表。我们标记当前节点已访问然后递归地访问所有它能到达且未被访问的邻居节点。3.4 主逻辑枚举起点并检查现在我们将所有部分组合起来完成主逻辑。// 枚举每一个塔作为起点 for (int start 0; start N; start) { // 每次搜索前重置访问标记数组 visited.assign(N, false); // 使用assign高效重置所有值为false // visited vectorbool(N, false); // 另一种写法但可能效率略低 // 从起点开始深度优先搜索 dfs(start, graph); // 检查是否所有塔都被访问到 bool all_covered true; for (bool v : visited) { if (!v) { all_covered false; break; } } // 如果全部覆盖输出结果编号从1开始 if (all_covered) { cout start 1 endl; // 转换为1-based索引 return 0; // 找到即结束程序 } } // 如果循环结束都没找到输出-1 cout -1 endl; return 0;实操心得visited.assign(N, false)比在循环内重新构造vectorbool(N, false)通常效率更高因为它可能复用已分配的内存。判断是否全部覆盖的循环可以在dfs函数内部加入一个计数器当计数器达到N时提前终止搜索进行剪枝。但对于N1000差别不大清晰的逻辑更重要。输出格式务必注意题目要求的输出是塔的编号而我们的数组索引是从0开始的所以输出时要1。这是一个常见的“差一错误”Off-by-one error陷阱。3.5 完整代码整合将上述所有部分整合就得到了完整的AC代码。#include iostream #include vector #include cmath #include cstring using namespace std; struct Tower { int x, y, r; }; vectorbool visited; void dfs(int u, const vectorvectorint g) { visited[u] true; for (int v : g[u]) { if (!visited[v]) { dfs(v, g); } } } int main() { int N; cin N; vectorTower towers(N); for (int i 0; i N; i) { cin towers[i].x towers[i].y towers[i].r; } // 1. 建图 vectorvectorint graph(N); for (int i 0; i N; i) { for (int j 0; j N; j) { if (i j) continue; long long dx towers[i].x - towers[j].x; long long dy towers[i].y - towers[j].y; long long dist_sq dx * dx dy * dy; long long r_sq (long long)towers[i].r * towers[i].r; if (dist_sq r_sq) { graph[i].push_back(j); } } } // 2. 枚举起点并检查 for (int start 0; start N; start) { visited.assign(N, false); dfs(start, graph); bool ok true; for (bool v : visited) { if (!v) { ok false; break; } } if (ok) { cout start 1 endl; return 0; } } // 3. 无解情况 cout -1 endl; return 0; }4. 算法复杂度分析与优化探讨写完代码我们有必要分析一下它的效率看看在极限数据下是否可行以及有没有优化空间。4.1 时间复杂度分析我们的算法主要分为两步建图双重循环遍历所有塔对复杂度是 O(N²)。对于每一对我们进行常数次整数运算加减乘除和比较。因此建图部分是 O(N²)。枚举与遍历最坏情况下我们需要枚举N个起点。对于每个起点进行一次DFS或BFS。DFS/BFS遍历图的时间复杂度是 O(VE)其中V是顶点数NE是边数。在最坏情况下每个塔都能覆盖其他所有塔那么边数E ≈ N²。因此一次DFS的复杂度是 O(N N²) O(N²)。枚举N次总复杂度就是 O(N * N²) O(N³)。当 N1000 时N³ 10^9这显然会超时一般竞赛时间限制1秒可承受操作次数在10^7~10^8量级。所以我们上面的朴素算法在理论最坏情况下是不可行的。但为什么很多同学用类似代码能AC呢这是因为实际数据不会达到这种最坏情况。出题人往往会控制数据的强度使得平均边数远小于N²或者存在其他特性。然而依赖数据强弱不是好习惯我们应该思考更优的解法。4.2 优化策略逆向思维与预处理一个经典的优化策略是逆向思考。我们原本的问题是“是否存在一个起点能到达所有点”。这等价于“是否存在一个点所有其他点都能到达它”吗不完全是因为边是有向的。但我们可以考虑图的强连通分量SCC。如果我们将原图求强连通分量并缩点形成一个有向无环图DAG。那么原问题有解等价于在DAG中存在一个源点入度为0的强连通分量并且从这个源点对应的强连通分量中的任意一点出发能到达所有其他点。更进一步在DAG中如果存在一个源点能到达所有点那么这个源点是唯一的否则两个源点互不可达。因此算法可以优化为使用Kosaraju或Tarjan算法求原图的强连通分量并缩点。检查缩点后的DAG中入度为0的强连通分量是否只有一个。如果不是一个直接输出-1因为多个源点无法互相到达。如果只有一个入度为0的分量则检查这个分量中的任意一个原始顶点比如第一个顶点从它出发进行DFS看是否能访问所有N个原始顶点。如果可以输出该顶点编号否则输出-1。这个算法的时间复杂度为 O(N²)建图 O(NE)求SCC和DFS在N1000时是完全可以接受的。这大大降低了最坏情况下的复杂度。4.3 另一种思路传递闭包与bitset优化对于N1000我们还可以考虑使用传递闭包的优化版本。朴素传递闭包如Floyd-Warshall是O(N³)不行。但我们可以用bitset来加速。bitsetN可以看作一个长度为N的二进制位数组它支持高效的位运算与、或、移位。我们可以用bitset来表示每个节点能到达的节点集合。设reach[i]为一个bitset初始时reach[i][i] 1并且如果存在边i-j则reach[i][j] 1。然后我们可以用类似动态规划或迭代的方式通过位运算来更新可达集合。例如如果存在边i-k那么i能到达的集合应该包含k能到达的集合。这可以通过reach[i] | reach[k]来实现。我们需要以某种顺序例如拓扑序但图可能有环多次迭代直到所有reach集合不再变化。这个过程类似于求有向图的传递闭包但利用bitset的位并行可以将复杂度从O(N³/word_size)大约优化到O(N³/64)。对于N1000这大约是(10^9)/64 ≈ 1.6e7次操作在优化良好的C中是有可能卡时间通过的。但这需要更精巧的实现且不如SCC缩点的方法直观和稳定。给初学者的建议在竞赛中如果时间紧迫可以先实现朴素的O(N³)枚举DFS。因为很多比赛的数据不会卡满最坏情况。提交后如果超时再考虑优化为SCC缩点法。平时练习则应该力求掌握更优的解法。5. 常见错误与调试技巧实录在实际编写和提交代码的过程中即使是思路正确的程序也常常因为一些细节问题导致WA错误答案或TLE超时。下面我总结几个这道题常见的“坑”。5.1 精度问题与整数溢出这是最隐蔽的错误之一。// 错误示例使用int和sqrt int dx towers[i].x - towers[j].x; int dy towers[i].y - towers[j].y; double dist sqrt(dx*dx dy*dy); // 若dx*dx超过int范围则溢出 if (dist towers[i].r) { ... } // 浮点数比较可能存在精度误差解决方法如前所述使用long long存储平方值并比较平方值。long long dx (long long)towers[i].x - towers[j].x; long long dy (long long)towers[i].y - towers[j].y; long long dist_sq dx*dx dy*dy; long long r_sq (long long)towers[i].r * towers[i].r; if (dist_sq r_sq) { ... } // 安全无精度问题5.2 有向边与无向边的混淆题目明确是“塔i广播能覆盖到塔j”这是单向关系。如果错误地建成了无向边那么只要整个图是连通的无向意义下从任意点出发都能到达所有点这显然会得到错误答案。务必仔细审题。5.3 索引转换错误输入和存储用0-based索引输出要求1-based索引。忘记1就会输出错误答案。这是一个低级但常见的错误。5.4 未重置访问数组在枚举每个起点时必须将visited数组全部重置为false。如果忘记重置上一次搜索的结果会影响下一次导致逻辑错误。使用visited.assign(N, false)是清晰的做法。5.5 递归深度过大虽然N≤1000但在极端情况下比如一条链状的覆盖关系DFS的递归深度可能达到1000。这对于大多数评测系统的栈空间来说通常是足够的一般默认栈空间几MB到几十MB。但如果担心栈溢出可以采用以下方法使用显式栈实现迭代版DFS。使用BFS它天然使用队列没有递归深度问题。迭代DFS示例void dfs_iter(int start, const vectorvectorint g) { vectorbool vis(N, false); stackint stk; stk.push(start); vis[start] true; while (!stk.empty()) { int u stk.top(); stk.pop(); // 注意这里出栈顺序与递归顺序略有不同但不影响连通性判断 for (int v : g[u]) { if (!vis[v]) { vis[v] true; stk.push(v); } } } visited vis; // 更新全局或外部visited }5.6 输入输出效率对于C在数据量较大时虽然本题N1000不大可以关闭C标准流与C标准流的同步来提升cin/cout的速度。ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);将这行代码放在main函数开头。注意使用了这行代码后就不要混用cin/cout和scanf/printf了。5.7 调试方法当程序结果不对时可以构造小数据进行测试。最小测试N1。一个塔应该输出1。简单测试N2。塔0覆盖塔1塔1不覆盖塔0。起点应为0。无解测试N2。两个塔互相都覆盖不到。应该输出-1。对称测试N2。两个塔互相覆盖。起点0或1都应该可以但按题目枚举顺序输出较小的编号1。可以编写一个简单的生成测试数据的程序或者手动计算然后用你的程序跑对比预期输出。我个人在开发这类算法题时习惯先写一个debug函数把建好的图打印出来看看确保边的方向正确。例如void printGraph(const vectorvectorint g) { for (int i 0; i g.size(); i) { cout i - ; for (int v : g[i]) cout v ; cout endl; } }在关键步骤后调用它能快速定位建图逻辑的错误。6. 从本题延伸的算法学习路径解决P10043“广播”这道题绝不仅仅是为了AC。它像一把钥匙能打开图论算法学习的几扇重要大门。6.1 图论基础概念的巩固这道题完美串联了以下概念有向图 vs 无向图明确边的方向性对问题建模的决定性影响。邻接表存储学会使用vectorvectorint来存储稀疏图这是竞赛中最常用的存图方式务必熟练掌握。图的遍历DFS和BFS是图论算法的基石。本题提供了绝佳的练习场景你需要决定递归还是迭代并理解它们的时间复杂度。可达性这是图论的一个基本问题。本题是单源可达性你还可以思考多源可达性哪些点能被一组起点到达如何求解。6.2 向更高级算法的迈进在尝试优化时我们自然接触到了强连通分量SCCTarjan算法或Kosaraju算法。理解SCC的概念和求解方法是解决许多有向图复杂问题如2-SAT的关键。缩点后得到DAG往往能简化问题。拓扑排序在DAG上拓扑排序能给出一个线性序列。本题优化算法中虽然不显式需要拓扑排序但理解DAG的性质是思考的基础。bitset优化这是一种用空间换时间并利用计算机位并行指令加速集合运算的高级技巧。在状态压缩、传递闭包等场景下非常有效。6.3 建立“建模-抽象-算法选择”的思维流程这道题最大的价值在于训练解题思维问题抽象将“广播覆盖”转化为“有向图可达性”。这种从具体场景中提取数学模型的能力是解决所有算法题的核心。暴力起步先想出最直观的解法枚举DFS并分析其复杂度。不要一开始就追求最优解。寻找优化当发现朴素解法复杂度高时分析瓶颈本题是O(N³)的枚举然后思考图论中是否有现成的工具SCC可以消除冗余计算将多个必须一起遍历的点打包。代码实现与调试将优化后的思路转化为准确、高效的代码并处理边界情况。6.4 推荐的相关练习题目为了巩固从本题学到的知识可以尝试以下题目信奥P2863 [USACO06JAN] The Cow Prom求有向图中大小大于1的强连通分量数量。Tarjan算法的模板题。信奥P2341 [USACO03FALL / HAOI2006] 受欢迎的牛经典题考察SCC缩点后DAG的性质。如果本题的“广播”是双向覆盖无向边就变成了求能否从一个点到达所有点这实际上是求图的“连通性”或“度数”是另一类问题。信奥P3916 图的遍历反向建图DFS另一种思考可达性问题的方式。Codeforces 题目“Radio Stations”虽然不直接相关但涉及覆盖和选择问题可以锻炼类似的建模能力。刷题不在多而在精。把一道像“广播”这样的题吃透理解其各种解法和优化思路远比盲目刷十道模板题收获更大。在实现SCC优化版本时你可能会遇到栈溢出、细节错误等问题耐心调试并理解每一行代码的作用这个过程本身就是极好的训练。最后记得在AC之后去题解区看看其他选手的思路博采众长你的进步会更快。