OPTSUB - Optimal Connected Subset

no tags 

  • A point P(x,y) is called an integer point if and only if both x and y are integers.
  • W is the set which contains all the integer points on the plane.
  • Two integer point P(x,y) and Q(x',y') are called adjacent if and only if |x-x'|+|y-y'|=1.
  • S is a set of integer points if and only if S is a limited subset of W.
  • If S is a set of integer points, R and T belong to S,and there exist a limited integer point sequence Q0(=R),Q1,Q2,...,Qk,Qk+1(=T) which satisfies that
    • Qi!=Qj iff i!=j
    • Qi and Qi+1 are adjacent, for each 0<=i<=k.
    • Qi belongs to S, for each 0<=i<=k+1.
    we call R and T are connected and the sequence Qi(0<=i<=k) is a path that connect R and T.
  • If S is a set of integer points, X and Y are some integer points that belong to S, there exists one and only one path connected X and Y, then S is called an optimal set.

Given an optimal set V, your task is to find an optimal set B, satisfying that B is a subset of V and the sum of the weights of each integer point is maximum.


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). N lines follow, each contains 3 integers, the X-coordinate, the Y-coordinate and the weight(the absolute value of the weight<=100) of the ith integer point, separated by single spaces.


T lines,each contains a single integer - the maximum sum of weights.


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


hide comments
Luke Pebody: 2011-05-26 13:55:20

The final part of the definition says "one and only one path"

:D: 2010-05-29 14:39:09

There can be multiple paths in optimal set. The definition doesn't say anything about one path and the example ((0,0),(0,1),(1,0),(1,1),(2,0)) meets the definion. One point set is an optimal set, because there are no two different points R and T, so the definion is meet by default.

Luke Pebody: 2010-05-13 10:55:46

Also, is a set of 1 point optimal?

Luke Pebody: 2010-05-13 10:54:41

Does an optimal set just have 2 points with only one path between them, or do all pairs of points have only one path. For instance, is (0,0),(0,1),(1,0),(1,1),(2,0) an optimal set?

Added by:Fudan University Problem Setters
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