NOI '99 P5 - Optimally Connected Subset

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 16M

Problem type
National Olympiad in Informatics, China, 1999

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 P_1(x_1, y_1), P_2(x_2, y_2), if |x_1-x_2| + |y_1-y_2| = 1, then P_1 and P_2 shall be considered neighbors, which is denoted as P_1 \sim P_2. Otherwise, P_1 and P_2 are considered non-neighboring.

Definition 2: The set S is a finite subset of W such that S = \{P_1, P_2, \dots, P_n\} (n \ge 1), where P_i (1 \le i \le 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 Q_1, Q_2, \dots, Q_k satisfying the following:

  1. Q_i belongs to S (1 \le i \le k);
  2. Q_1 = R, Q_k = T;
  3. Q_i \sim Q_{i+1} (1 \le i \le k-1) — i.e. Q_i and Q_{i+1} are neighbors; and
  4. Q_i \ne Q_j for any 1 \le i < j \le k.

then we shall say that R and T are connected within set S, where the sequence Q_1, Q_2, \dots, Q_k 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:

  1. B is a subset of V;
  2. any two integer points in B are connected within B; and
  3. out of the set of integer points satisfying 1. and 2., B is the set where the total score is highest.

Input Specification

Line 1 contains an integer N (2 \le N \le 1\,000), the number of points in V. Within the following N lines, the i-th line (1 \le i \le N) contains three space-separated integers X_i, Y_i, and C_i (-10^6 \le X_i, Y_i \le 10^6; -100 \le C_i \le 100), representing the coordinates of the i-th point along with its score.

Output Specification

The output should consist of one integer, the total score of the optimally connected subset.

Sample Input

5
0 0 -2
0 1 1
1 0 1
0 -1 1
-1 0 1

Sample Output

2

Problem translated to English by Alex.


Comments

There are no comments at the moment.