Moocast

题目描述

Farmer John 的 $N$ 头奶牛（$1 \leq N \leq 200$）想要组织一个紧急“moo-cast”系统，用于在它们之间广播重要消息。

与其在很远的距离上彼此哞叫，奶牛们决定为自己配备对讲机，每头奶牛一台。这些对讲机都有有限的传输半径——功率为 $P$ 的对讲机只能向距离不超过 $P$ 的其他奶牛发送信号（注意：由于奶牛 A 的功率可能大于奶牛 B，奶牛 A 可能可以向奶牛 B 发送信号，即使奶牛 B 不能向奶牛 A 发送信号）。幸运的是，奶牛们可以沿着由若干次中继组成的路径相互转发消息，因此并不需要每头奶牛都能直接向每一头其他奶牛发送。

由于对讲机传输具有不对称性，考虑中继后，从某些奶牛发起的广播在触达大量接收者方面可能比其他奶牛更有效。请帮助奶牛们确定：从单头奶牛发起广播，最多能触达多少头奶牛。

输入格式

第一行输入为 $N$。 接下来 $N$ 行每行包含一头奶牛的 $x$ 和 $y$ 坐标（整数，范围为 $0 \ldots 25,000$），以及 $p$，表示该奶牛所持对讲机的功率。

输出格式

输出一行，包含从单头奶牛发起的广播最多能触达的奶牛数量。发起广播的奶牛也计入该数量中。

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

3

提示

在上面的例子中，从奶牛 1 发起的广播总共可以触达 3 头奶牛（包括奶牛 1）。 题目鸣谢：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver