解题思路

将每个能源站视作图中的一个节点。若从站点 i 出发，其激活半径为 $r\_i$，则对任意站点 j，当 $(x_i - x_j)^2 + (y_i - y_j)^2 \le r_i^2$ 时，在图中加入一条有向边 i → j。激活规则：从某个初始节点出发，沿有向边可达的所有节点均被视为“激活”节点。

算法步骤

1. 读入数据 读取整数 n，以及三元组 $(x\_i, y\_i, r\_i)$，$i=1,2,\dots,n$。
2. 建立邻接表 双重循环枚举所有 $(i,j)$ 对，计算 $(x_i - x_j)^2 + (y_i - y_j)^2$ 与 $r\_i^2$ 的大小关系，若前者不大于后者，则在 i 的邻接表中加入 j。
3. 模拟激活 对每个起始节点 i，使用 BFS（或 DFS）从 i 出发，遍历所有可达节点，统计激活节点数 $\mathrm{cnt}\_i$。
4. 取最大值 输出最大激活数： $\max_{1\le i\le n}\mathrm{cnt}_i$

复杂度分析

• 建图：$O(n^2)$，双重循环枚举所有 $(i,j)$ 对。
• 遍历：对每个起始节点执行一次 BFS/DFS，单次时间 $O(n + m)\approx O(n^2)$，共 $n$ 次，合计 $O(n^3)$。
• 总时间复杂度：$O(n^3)$，在 $n\le100$ 时可行（$n^3\le10^6$）。
• 空间复杂度：邻接表存储 $O(n^2)$ 条边，额外使用 $O(n)$ 的标记数组，总体 $O(n^2)$。

代码实现

Python

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    idx = 1
    for _ in range(t):
        n = int(data[idx]); idx += 1
        x = [0]*n
        y = [0]*n
        r = [0]*n
        for i in range(n):
            x[i] = int(data[idx]); y[i] = int(data[idx+1]); r[i] = int(data[idx+2])
            idx += 3
        # 建图
        g = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                dx = x[i] - x[j]
                dy = y[i] - y[j]
                if dx*dx + dy*dy <= r[i]*r[i]:
                    g[i].append(j)
        # 对每个起点做广度优先搜索
        ans = 1
        for s in range(n):
            vis = [False]*n
            q = deque([s])
            vis[s] = True
            cnt = 1
            while q:
                u = q.popleft()
                for v in g[u]:
                    if not vis[v]:
                        vis[v] = True
                        cnt += 1
                        q.append(v)
            if cnt > ans:
                ans = cnt
        print(ans)

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            long[] x = new long[n], y = new long[n], r = new long[n];
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextLong();
                y[i] = sc.nextLong();
                r[i] = sc.nextLong();
            }
            // 建图
            List<Integer>[] g = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    long dx = x[i] - x[j];
                    long dy = y[i] - y[j];
                    if (dx*dx + dy*dy <= r[i]*r[i]) {
                        g[i].add(j);
                    }
                }
            }
            // BFS 计算最大激活数
            int ans = 1;
            for (int s = 0; s < n; s++) {
                boolean[] vis = new boolean[n];
                Queue<Integer> q = new LinkedList<>();
                q.add(s);
                vis[s] = true;
                int cnt = 1;
                while (!q.isEmpty()) {
                    int u = q.poll();
                    for (int v : g[u]) {
                        if (!vis[v]) {
                            vis[v] = true;
                            cnt++;
                            q.add(v);
                        }
                    }
                }
                ans = Math.max(ans, cnt);
            }
            System.out.println(ans);
        }
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> x(n), y(n), r(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i] >> r[i];
        }
        // 建图
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                if (dx*dx + dy*dy <= r[i]*r[i]) {
                    g[i].push_back(j);
                }
            }
        }
        // BFS 计算最大激活数
        int ans = 1;
        for (int s = 0; s < n; s++) {
            vector<bool> vis(n, false);
            queue<int> q;
            q.push(s);
            vis[s] = true;
            int cnt = 1;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        cnt++;
                        q.push(v);
                    }
                }
            }
            ans = max(ans, cnt);
        }
        cout << ans << "\n";
    }

    return 0;
}

题目内容

在二维地图上，有 $n$ 个能源站，能源站的的坐标依次为 $(x_1, y_1),(x_2, y_2),...,(x_n,y_n)$

一开始所有的能源站都是关闭状态.若能源站 $i$ 变为开启状态,则能源站 $i$ 能够把距离(直线距离)它不超过 $r_i$ 的所有能源站也变为开启状态，然后新启动的能源站也有可能继续把其它能源站变为开启状态。

多多现在能够开启任意一个能源站,请你告诉它最多能使多少个能源站变为开启状态。

输入描述

第一行一个整数 $T(1≤T≤10)$ ，接下来有 $T$ 组数据

每组数据第一行一个整数 $n(1 ≤n≤100)$

接下来 $n$ 行，每行 $3$ 个整数 $x_i,y_i,r_i$ $(0 ≤ x_i,y_i≤10^9)$ $(1≤r_i≤10^9)$

输出描述

对于每组数据，输出一行，每行一个数，表示最多能使多少个能源站变为开启状态

样例1

输入

3
2
0 0 1
2 0 1
3
0 0 1
1 0 1
3 0 1
4
0 0 4
2 0 1
3 0 1
5 0 1

输出

1
2
3

说明

第一组：多多开启"$1$"；总共开启 $1$ 个

第二组：多多开启"$1$”，"$1$”开启"$2$"；总共开启 $2$ 个

第三组数据：多多开启"$1$"，"$1$"开启"$2$”、“$3$”；总共开启 $3$ 个