紧急广播系统(Emergency Moo-cast System)

题目背景

农夫约翰有 N 头奶牛(1 ≤ N ≤ 200),它们需要建立一个紧急广播系统,用于在牧场中快速传递重要消息。每头奶牛配备一部单向对讲机,其传输能力由功率 P 决定:

  • 如果奶牛 A 的功率为 P,它能将消息直接传递给距离 ≤ P 的其他奶牛(但 B 不一定能回传,除非 B 的功率足够)。
  • 消息可以通过中继转发(多跳传播)扩大覆盖范围。

目标:计算从任意一头奶牛出发的单次广播,最多能覆盖多少头奶牛(包括直接和间接可达的)。


中译中(关键概念解析)

1. 单向传输

  • 奶牛 A 能传消息给 B,但 B 不一定能传回 A(除非 B 的功率足够覆盖 A)。
  • 例如:A 的功率为 5,B 的功率为 3,A→B 距离为 4:
    • A 能传 B(4 ≤ 5),但 B 不能传 A(4 > 3)。

2. 中继传播

  • 消息可通过多跳传递。例如:A→B→C,即使 A 不能直接传 C,只要 A 能传 B,且 B 能传 C,则 C 仍能被覆盖。

3. 覆盖范围

  • 从某头奶牛出发,通过直接或中继方式能到达的所有奶牛数量,称为该奶牛的覆盖数。
  • 题目要求找出所有奶牛中最大的覆盖数。

输入输出格式+样例

输入格式

第一行,一个整数 N。

接下来 NN 行,第 ii 行包括第 ii 只牛的坐标 (xi,yi)(x_i,y_i),以及这只牛所持有对讲机的功率 PiP_i

输出格式

一行,一个整数,表示从来自单个奶牛的广播可以达到的奶牛的最大数量。

开始的牛也包括在这个数量中。

测试样例

输入

4
1 3 5
5 4 3
7 2 1
6 1 1

输出

3

数据范围

对于 100%100\% 的数据,N200N\le200i[1,N]\forall i \in [1,N]0xi,yi250000\le x_i,y_i\le25000

0 comments

No comments so far...

Information

ID
2480
Time
1000ms
Memory
256MiB
Difficulty
3
Tags
# Submissions
6
Accepted
3
Uploaded By