为了方便你创建 OJ（Online Judge）测试数据，我编写了此数据生成器。它包含了标准 BFS 算法逻辑（用于生成 .out）以及针对性数据构造逻辑（用于生成 .in）。

数据生成策略

1. Case 1-3：完全对应题目给出的 3 个原始样例。
2. Case 4 (最小边界)：$n=1$，测试基础逻辑。
3. Case 5 (完全独立)：$n=100$，所有炸弹坐标极远，半径极小，测试最大值为 1 的情况。
4. Case 6 (长链引爆)：$n=1000$，炸弹排成一线，每个只能引爆下一个，测试线性深度。
5. Case 7 (稠密团块)：$n=500$，大量炸弹重合或半径覆盖全场，测试 $O(N^3)$ 的密集情况。
6. Case 8 (大规模随机 - 稀疏)：$n=2100$，坐标范围大，半径小。
7. Case 9 (大规模随机 - 稠密)：$n=2100$, 坐标中等，半径较大。
8. Case 10 (多簇分布)：$n=2100$，将炸弹分布在几个特定的坐标簇中，测试复杂连通性。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

struct Bomb {
    ll x, y, r;
};

// --- 标准 BFS 解法，用于生成正确答案 ---
int solve_std(int n, const vector<Bomb>& b) {
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            ll dx = b[i].x - b[j].x;
            ll dy = b[i].y - b[j].y;
            if (dx * dx + dy * dy <= b[i].r * b[i].r) {
                adj[i].push_back(j);
            }
        }
    }

    int max_cnt = 0;
    for (int i = 0; i < n; i++) {
        vector<bool> vis(n, false);
        queue<int> q;
        q.push(i);
        vis[i] = true;
        int cur_cnt = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            cur_cnt++;
            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
        max_cnt = max(max_cnt, cur_cnt);
        if (max_cnt == n) break; // 剪枝
    }
    return max_cnt;
}

// --- 数据写入函数 ---
void write_case(int id, int n, const vector<Bomb>& b) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    ofstream fout(in_name);
    fout << n << "\n";
    for (int i = 0; i < n; i++) {
        fout << b[i].x << " " << b[i].y << " " << b[i].r << "\n";
    }
    fout.close();

    ofstream fans(out_name);
    fans << solve_std(n, b) << endl;
    fans.close();
    cout << "Case " << id << " [N=" << n << "] generated." << endl;
}

int main() {
    mt19937 rng(time(0));

    // Case 1, 2, 3: 原始样例
    write_case(1, 2, {{1, 2, 3}, {2, 3, 1}});
    write_case(2, 2, {{2, 1, 3}, {6, 1, 4}});
    write_case(3, 5, {{1, 1, 5}, {10, 10, 5}, {2, 1, 10}, {3, 3, 0}, {5, 12, 12}});

    // Case 4: n=1
    write_case(4, 1, {{100, 100, 10}});

    // Case 5: 互不干扰
    {
        int n = 100;
        vector<Bomb> b;
        for(int i=0; i<n; i++) b.push_back({(ll)i*1000, (ll)i*1000, 1});
        write_case(5, n, b);
    }

    // Case 6: 长链引爆 (0->1->2->...->n-1)
    {
        int n = 1000;
        vector<Bomb> b;
        for(int i=0; i<n; i++) b.push_back({(ll)i*10, 0, 10});
        write_case(6, n, b);
    }

    // Case 7: 密集团块
    {
        int n = 500;
        vector<Bomb> b;
        for(int i=0; i<n; i++) b.push_back({500, 500, 100000});
        write_case(7, n, b);
    }

    // Case 8: 大规模随机 - 稀疏
    {
        int n = 2100;
        vector<Bomb> b;
        for(int i=0; i<n; i++) 
            b.push_back({(ll)(rng()%100000), (ll)(rng()%100000), (ll)(rng()%100)});
        write_case(8, n, b);
    }

    // Case 9: 大规模随机 - 稠密
    {
        int n = 2100;
        vector<Bomb> b;
        for(int i=0; i<n; i++) 
            b.push_back({(ll)(rng()%5000), (ll)(rng()%5000), (ll)(rng()%2000)});
        write_case(9, n, b);
    }

    // Case 10: 多簇分布
    {
        int n = 2100;
        vector<Bomb> b;
        ll centers[3][2] = {{1000, 1000}, {50000, 50000}, {90000, 1000}};
        for(int i=0; i<n; i++) {
            int c = i % 3;
            b.push_back({centers[c][0] + (rng()%500), centers[c][1] + (rng()%500), (ll)(rng()%600)});
        }
        write_case(10, n, b);
    }

    return 0;
}

生成器设计要点说明：

1. 文件大小控制：
   • $N=2100$ 的数据量，每个炸弹三个整数。在 .in 文件中，每行约 15-20 字节。
   • $2100 \times 20 = 42,000$ 字节（约 40 KB）。
   • 10 个测试点总大小约 400 KB，远低于 2MB 限制，非常轻量。
2. 区分度设计：
   • Case 6 (长链)：专门对付那些没有正确处理递归深度或者搜索方向的程序。
   • Case 7 & 9：测试 $O(N^3)$ 复杂度。如果选手的 BFS 写得常数过大，或者在 $N=2100$ 时重复建图，可能会面临 TLE。
   • Case 8：测试大坐标下的 long long 溢出。如果选手用了 int 来计算距离平方，会得到错误结果。
3. 计算安全：
   • 使用了非递归的 BFS 逻辑来生成答案，避免了生成器自身在大规模数据（如 Case 6）下爆栈。
   • 所有距离计算均采用 long long，确保 .out 文件的绝对准确性。
4. 无异常处理：
   • 代码中没有除法运算，有效规避了“除以 0”的异常。

使用方法：

1. 在本地 C++ 环境（支持 C++11 或以上）编译运行此代码。
2. 运行后，当前目录会产生 1.in/out 到 10.in/out。
3. 将这些文件上传到 OJ 系统作为测试数据即可。

在 NOI 竞赛中，当 $N$ 达到 $2000$ 以上且图可能非常稠密时，$O(N^3)$ 的暴力 BFS 可能会面临时间紧迫的问题。此时，利用 强连通分量 (SCC) 缩点 + Bitset 优化传递闭包 是图论中最顶级的优化手段。

以下是版本二的完整标准代码。

版本二：SCC 缩点 + Bitset 拓扑 DP（最优复杂度版）

核心逻辑：

1. Tarjan 缩点：有向图中可能存在环。如果 A、B、C 形成环，引爆其中任何一个都会引爆全环。缩点将环变成一个点，原图转化为 DAG（有向无环图）。
2. Bitset 优化：在 DAG 上，一个点能到达的节点集合 = 自身包含的节点 $\cup$ 所有后继节点能到达的集合。
3. 位运算加速：使用 std::bitset 的 |（按位或）操作，可以将 $O(N)$ 的集合合并优化到 $O(N/64)$。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <bitset>

using namespace std;

typedef long long ll;

struct Bomb {
    ll x, y, r;
};

int n;
Bomb b[2105];
vector<int> adj[2105];      // 原图
vector<int> dag[2105];     // 缩点后的 DAG
int dfn[2105], low[2105], timer;
bool in_stack[2105];
stack<int> st;
int scc[2105], scc_cnt;
bitset<2105> reach[2105];  // 每个 SCC 能到达的原始节点集合
int in_degree[2105];

// 几何判断
bool can_detonate(int i, int j) {
    ll dx = b[i].x - b[j].x;
    ll dy = b[i].y - b[j].y;
    return dx * dx + dy * dy <= b[i].r * b[i].r;
}

// Tarjan 算法找强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    in_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int node = st.top();
            st.pop();
            in_stack[node] = false;
            scc[node] = scc_cnt;
            reach[scc_cnt].set(node); // 初始：SCC 包含其内部的原始节点
            if (node == u) break;
        }
    }
}

// 记忆化搜索进行 DAG 上的 Bitset 传递闭包计算
void dfs_dag(int u) {
    static bool visited[2105];
    if (visited[u]) return;
    visited[u] = true;

    for (int v : dag[u]) {
        dfs_dag(v);
        reach[u] |= reach[v]; // 关键优化：按位或操作加速集合合并
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++)
        cin >> b[i].x >> b[i].y >> b[i].r;

    // 1. 建图 O(N^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && can_detonate(i, j)) {
                adj[i].push_back(j);
            }
        }
    }

    // 2. 缩点 O(N+E)
    for (int i = 0; i < n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 3. 建立 DAG O(N+E)
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            if (scc[u] != scc[v]) {
                dag[scc[u]].push_back(scc[v]);
            }
        }
    }
    
    // 去重 DAG 边（可选，能微弱提升性能）
    for (int i = 1; i <= scc_cnt; i++) {
        sort(dag[i].begin(), dag[i].end());
        dag[i].erase(unique(dag[i].begin(), dag[i].end()), dag[i].end());
    }

    // 4. 计算每个 SCC 能到达的总节点数
    int ans = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        dfs_dag(i);
        ans = max(ans, (int)reach[i].count());
    }

    cout << ans << endl;

    return 0;
}

复杂度分析与思考过程

1. 时间复杂度

• 建图：$O(N^2)$。
• Tarjan 缩点：$O(N + E)$。
• Bitset 传递闭包：在 DAG 上进行 $E_{dag}$ 次 | 操作。每次 | 操作的复杂度是 $O(N/64)$。
• 总复杂度：$O(N^2 + \frac{E \cdot N}{64})$。
• 思考：对于 $N=2100$，$E$ 最大约为 $4 \times 10^6$。如果不使用 Bitset，复杂度是 $O(N \cdot E)$ 约 $8 \times 10^9$；使用 Bitset 后约 $1.3 \times 10^8$，在 1s 限制下非常稳健。

2. 空间复杂度

• Bitset 存储：reach[2105] 占用的内存为 $2100 \times 2100 / 8$ 字节 $\approx 551$ KB。
• 邻接表：最坏 $O(N^2)$，约几 MB。
• 总结：空间占用极小，远低于 NOI 常见的 128MB/256MB 限制。

算法优化建议

1. 关于 Bitset 传递闭包： 如果不想写缩点，也可以直接对原图运行 $N$ 次 BFS。但在某些极端的“深链”或者“大环”数据下，缩点后的 DAG 节点数会大幅减少，效率更高。
2. 提前终止： 在计算 reach[i].count() 时，如果发现已经等于 $N$，直接输出 $N$ 并退出程序。
3. 计算几何溢出： 再次强调，dx * dx + dy * dy 必须用 long long。如果使用 std::pow 或 sqrt，由于浮点数精度问题，可能会在某些测试点 WA。

总结：读题与解题关键词

1. “最大引爆数”：暗示我们要统计可达节点的并集大小。
2. “单向边”：看到单向边 + 最短路/可达性 $\rightarrow$ 联想到 DAG / 缩点。
3. “$N=2000$”：这是一个很微妙的数字。$O(N^2)$ 随便过，$O(N^3)$ 比较危险。在 NOI 竞赛中，这通常是 $O(N^3/w)$（即 Bitset）或者带优化的 $O(N^2)$ 的标志。
4. “欧几里得距离”：即 $\sqrt{(x1-x2)^2 + (y1-y2)^2} \le R$。永远记得把根号移项变成平方，以保持整数运算的精确性。

此题解涵盖了从基础建模到竞赛级常数优化的所有核心要点，适合作为 NOI 专题训练。

在 NOI 竞赛中，这道题属于典型的计算几何建模 + 图论遍历。由于 $N=2100$ 的规模，我们需要非常小心地处理时间复杂度的常数以及大整数溢出问题。

以下是从基础到竞赛级优化的题解。

版本一：标准 BFS（邻接表实现）

思路：

1. 建图：对每一对炸弹 $(i, j)$，判断 $i$ 是否能引爆 $j$。如果能，建立一条 $i \to j$ 的有向边。
2. 搜索：由于我们需要求引爆“任意一个”炸弹后的最大总数，我们必须以每个点作为起点跑一次 BFS/DFS。
3. 注意：距离平方计算必须使用 long long。

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

// 炸弹结构体
struct Bomb {
    ll x, y, r;
};

int n;
Bomb b[2105];
vector<int> adj[2105];
bool vis[2105];

// 核心几何判断：判断 bomb i 能否引爆 bomb j
bool can_detonate(int i, int j) {
    ll dx = b[i].x - b[j].x;
    ll dy = b[i].y - b[j].y;
    ll r = b[i].r;
    // 使用距离平方比较，避免开方带来的精度误差
    // 10^5 * 10^5 = 10^10, 必须用 long long
    return dx * dx + dy * dy <= r * r;
}

int bfs(int start) {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    
    q.push(start);
    vis[start] = true;
    int count = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        count++;
        
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return count;
}

int main() {
    // 竞赛必备优化：关闭同步流，提高读入速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) {
        cin >> b[i].x >> b[i].y >> b[i].r;
    }

    // 1. 建图：O(N^2)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (can_detonate(i, j)) {
                adj[i].push_back(j);
            }
        }
    }

    // 2. 遍历每个起点：O(N * (N+E))
    int max_bombs = 0;
    for (int i = 0; i < n; i++) {
        max_bombs = max(max_bombs, bfs(i));
        // 剪枝优化：如果已经能引爆所有炸弹，提前结束
        if (max_bombs == n) break; 
    }

    cout << max_bombs << endl;
    return 0;
}

• 时间复杂度：$O(N^2 + N \times E)$。最坏情况下 $E = N^2$，则为 $O(N^3)$。对于 $N=2100$，$N^3 \approx 9 \times 10^9$，但在实际测试中，邻接表 BFS 的常数极小，且图往往并不完全稠密，通常能过。
• 空间复杂度：$O(N^2)$，用于存储邻接表。

版本二：Bitset 传递闭包优化（针对稠密图）

思路： 在 NOI 中，如果要处理 $N=2000 \sim 3000$ 级别的有向图可达性问题，std::bitset 是提速的神器。

1. 求出强连通分量 (SCC) 并缩点，将原图转为有向无环图 (DAG)。
2. 在 DAG 上使用 bitset 进行动态规划，求出每个点能到达的所有点集合。
3. 利用 bitset.count() 快速获取结果。

注意： 此版本逻辑较复杂，适用于 $N$ 更大或时限更紧的情况。

// 伪代码提示 - NOI 进阶思路
/*
1. 使用 Tarjan 算法找到所有强连通分量 (SCC)。
2. 缩点，建立新图 (DAG)。
3. 每个 SCC 的 bitset 记录该分量内包含的原炸弹索引。
4. 按照逆拓扑序在 DAG 上进行 bitset 合并：
   dp[u] |= dp[v] (对所有 u->v 的边)
5. 最终结果 = max(dp[i].count())
*/

时间复杂度优化建议思考过程

1. 距离计算瓶颈： 建图是 $O(N^2)$ 的。在计算时，dx*dx + dy*dy 是固定开销。在某些计算几何题中，可以先对坐标进行排序或使用分块、四叉树优化，但在本题中由于是圆域判定，且 $N=2100$，直接 $N^2$ 建图是最稳的选择。

2. 搜索瓶颈：

   • BFS vs DFS：在统计可达点数量时，两者理论复杂度一致，但 BFS 对内存访问更友好。
   • 剪枝：如果某个炸弹 $i$ 在之前的某次搜索中被引爆过，且它属于某个强连通分量，那么从它出发能引爆的数量是固定的。这就是为什么缩点能显著提速。

3. 时间复杂度优化：

   • 如果 $N^3$ 实在跑不动，利用 bitset 可以将常数降低 $w=64$ 倍。对于 $9 \times 10^9$ 的操作量，优化后约 $1.4 \times 10^8$，在 1s 内是可以接受的。

读题关键词与易错点

1. “最大炸弹爆炸总数”：意味着我们需要统计的是去重后的节点总数，BFS/DFS 的 vis 数组就是为了解决去重。
2. “恰好一个”：确定了这是单源起点的搜索，我们需要枚举所有可能的起点。
3. “$x, y, r \le 10^5$”：
   • 关键陷阱：计算 r*r 达到 $10^{10}$。
   • 错误写法：int dist = dx*dx + dy*dy;（溢出为负数，导致判定错误）。
   • 正确写法：必须全线使用 long long。
4. 有向性：炸弹 A 能炸 B 不代表 B 能炸 A。在建图阶段，只能添加一条边。如果误写成无向图，样例 2 就会输出 2 而不是正确逻辑下的判断。

总结

对于 NOI 辅导：

• 初级：掌握两点间距离公式（距离平方比较法）和 BFS 建图遍历。
• 中级：处理 long long 溢出和 $O(N^3)$ 的常数优化技巧（如 std::vector 的 reserve 或提前 break）。
• 高级：理解有向图缩点和 bitset 优化传递闭包的工业级技巧。