#PQJ2586x15051. QOJ 2586_15051
QOJ 2586_15051
电信网络 电信网络 【问题描述】 JYY 创建的电信公司,垄断着整个JSOI 王国的电信网络。JYY 在JSOI 王 国里建造了很多的通信基站。目前所有的基站都是使用2G 网络系统的。而现在 3G 时代已经到来了,JYY 在思考,要不要把一些基站升级成3G 网络的呢? JSOI 王国可以被看作为一个无穷大的二维平面,JYY 一共建造了N 个通信 基站,第i 个基站的坐标是(Xi,Yi)。每个基站有一个通信范围Ri。第i 号基站会向 所有到其距离不超过Ri 的基站发送信息。 每个基站升级到3G 网络都会有一个收益Si,这个收益可能是正数(比如基 站附近有个大城市,用户很多,赚的流量费也就很多了),也可能是负数(比如 基站周围市场不佳,收益不能填补升级基站本身的投资)。 此外,由于原有的使用2G 网络系统的基站无法解析从升级成3G 网络系统 的基站所发来的信息(但是升级之后的基站是可以解析未升级基站发来的信息 的),所以,JYY 必须使得,在升级工作全部完成之后,所有使用3G 网络的基 站,其通信范围内的基站,也都是使用3G 网络的。 由于基站数量很多,你可以帮助JYY 计算一下,他通过升级基站,最多能 获得的收益是多少吗? 【输入格式】 从文件network.in 中读入数据。 输入文件的第一行一个整数N; 接下来N 行,每行4 个整数,Xi,Yi,Ri,Si,表示处在(Xi,Yi)的基站的通信 范围是Ri,升级可以获得的收益是Si。 数据满足任意两个基站的坐标不同。 【输出格式】 输出到文件network.out 中。 输出一行一个整数,表示可以获得的最大收益。 【样例输入】 5 0 1 7 10 0 -1 7 10 5 0 1 -15 10 0 6 10 15 1 2 -20
电信网络 【样例输出】 5 【样例说明】 我们可以将前三座基站升级成3G 网络,以获得最佳收益。 【数据规模】 对于30%的数据满足N ≤ 15; 对于50%的数据满足N ≤ 75; 对于100%的数据满足1 ≤ N ≤ 500,1 ≤ Ri ≤ 20000,|Xi|,|Yi|,|Si| ≤ 104。