All submissions for this problem are available.
In times of stone age, our ancestors used birds as medium of communication. Consider a network of houses inhabited by such ancestors and
each house having its own "messenger bird"
Every messenger bird has a certain limit of distance it can travel and can send the message to the neighboring houses only if the distance between the two houses is less than or equal to the messenger bird's travel limit.
Currently the ancestors use a certain species "A" of such messenger birds. A better species "B" is available which are easier to train than A. We need to decide which houses should upgrade their messenger birds from A to B under the following restriction:
If a house is using the new species B, then every house within its range must also use B so that the birds can be suitably identified in their locality as pertaining to messenger birds. The other way round is not necessary - i.e. houses using species A can send data to houses with B type messengers.
Given the above, we need to select the best set of houses which need to upgrade their bird species from A to B. There are benefits of the news species but also initial bird training costs. So each house will have a cost associated to it (positive or negative) which is the net value of upgrading the messenger bird of their house. Find out the set of houses that should upgrade their bird in order that the total cost of the up-gradation is maximized.
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains a single integer N denoting the number of houses. N lines follow. Each line consists of 4 integers: x, y, d, c. (x, y) corresponds to the coordinates of house, d is the messenger bird's travel limit and c is the cost of upgrading the messenger bird for that house.
- Output the total cost of the up-gradation
- 1 ≤ T ≤ 55
- 1≤ N ≤ 500
- -10 000 ≤ x, y ≤ 10 000
- 1 ≤ d ≤ 20 000
- -1000 ≤ c ≤ 1000
Input: 1 5 -1 1 8 6 0 -1 7 4 4 0 1 -16 9 1 5 14 14 1 4 -10 Output: 4
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.