P13451 [GCJ 2009 Finals] Wi-fi Towers

你将得到一个由无线信号塔组成的网络。每个信号塔都有一定的覆盖半径，并且只要相邻信号塔之间的距离不超过发送塔的覆盖半径，就可以向其发送数据。 这些信号塔目前使用的是旧的通信协议 $A$，但现在有一种更新、更好的协议 $B$ 可供升级。我们正在考虑将部分信号塔升级为协议 $B$，以获得更好的带宽。 但有一个重要的限制：如果某个信号塔 $T$ 升级为新协议 $B$，那么在 $T$ 覆盖范围内的所有信号塔也必须升级为协议 $B$，以便它们能够理解 $T$ 发送的数据。反过来则不要求——使用新协议 $B$ 的信号塔可以接收来自旧协议 $A$ 的信号。 你的任务是选择一组信号塔进行升级，使得升级后信号塔的总得分最大。每个信号塔升级的价值（即得分）可能为正也可能为负。你需要选择升级哪些信号塔，使得升级塔的总得分最大。

第一行为测试用例数 $T$。每组测试数据首先给出一个整数 $n$，表示信号塔的数量。接下来的 $n$ 行，每行包含 $4$ 个整数：$x$、$y$、$r$、$s$，分别表示信号塔的坐标 $(x, y)$，覆盖半径 $r$，以及升级该塔的得分 $s$。

对于每组测试数据，输出： Case #$X$: score 其中 $X$ 是测试编号（从 $1$ 开始），score 是你所能获得的最大总得分。

**限制条件** - $1 \leq T \leq 55$ - $-10000 \leq x, y \leq 10000$ - $1 \leq r \leq 20000$ - $-1000 \leq s \leq 1000$ - 不会有两个信号塔的坐标完全相同。 **小数据集（3 分）** - $1 \leq n \leq 15$ **大数据集（25 分）** - $1 \leq n \leq 500$ 翻译由 ChatGPT-4.1 完成。