- [USACO16DEC] Moocast S
英译中+中译中
- 2025-4-28 13:44:02 @
紧急广播系统(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。
接下来 行,第 行包括第 只牛的坐标 ,以及这只牛所持有对讲机的功率
输出格式
一行,一个整数,表示从来自单个奶牛的广播可以达到的奶牛的最大数量。
开始的牛也包括在这个数量中。
测试样例
输入
4
1 3 5
5 4 3
7 2 1
6 1 1
输出
3
数据范围
对于 的数据,,,。
0 comments
No comments so far...
Information
- ID
- 2480
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 6
- Accepted
- 3
- Uploaded By