OPTSUB - Optimal Connected Subset
It is well-known that we can uniquely represent any point P on the Cartesian coordinate system using an ordered pair (x, y). If both x and y are integers, then we shall call P an integer point, otherwise we shall call P a non-integer point. We shall denote all integer points on the plane using the set W.
Definition 1: For two points P1(x1, y1), P2(x2, y2), if |x1 − x2| + |y1 − y2| = 1, then P1 and P2 shall be considered neighbors, which is denoted as P1 ~ P2. Otherwise, P1 and P2 are considered non-neighboring.
Definition 2: The set S is a finite subset of W such that S = {P1, P2, …, Pn} (n ≥ 1), where Pi (1 ≤ i ≤ n) belongs in W. We shall call S a set of integer points.
Definition 3: Where S is a set of integer points, if the points R and T belong to S, and there exists a finite sequence Q1, Q2, …, Qk satisfying the following:
- Qi belongs to S (1 ≤ i ≤ k);
- Q1 = R, Qk = T;
- Qi ~ Qi+1 (1 ≤ i ≤ k−1) — i.e. Qi and Qi+1 are neighbours; and
- Qi ≠ Qj for any 1 ≤ i < j ≤ k
then we shall say that R and T are connected within set S, where the sequence Q1, Q2, …, Qk shall be called a pathway connecting points R and T.
Definition 4: For a set of integer points V, if for any two of V's integer points there exists exactly one pathway connecting them, then V shall be known as a singular set of integer points.
Definition 5: For any integer point on the plane, we can assign it an integer score. Thus, we shall call the sum of the scores of all the points in a set of integer points its total score.
Given a singular set of integer points V, we would like to find the optimally connected subset B, where:
- B is a subset of V;
- any two integer points in B is connected within B; and
- out of the set of integer points satisfying 1 and 2, B is the set where the total score is highest.
Input
The very first line of the input contains a single integer T, the number of test cases. T blocks follow.
For each test case, the first line contains a single integer N = |V| (N <= 1000). Within the following N lines, the i-th line (1 ≤ i ≤ N) contains three space-separated integers Xi, Yi, and Ci (−106 ≤ Xi, Yi ≤ 106; −100 ≤ Ci ≤ 100), representing the coordinates of the i-th point along with its score.
Output
T lines, each line should consist of one integer, the total score of the optimally connected subset.
Example
Input: 1 5 0 0 -2 0 1 1 1 0 1 0 -1 1 -1 0 1 Output: 2
Added by: | Fudan University Problem Setters |
Date: | 2007-04-01 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO |
Resource: | Chinese National Olympiad in Informatics 1999,Day 2; translated by Blue Mary |