OPTSUB - Optimal Connected Subset
- 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.
- 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.
Input: 1 5 0 0 -2 0 1 1 1 0 1 0 -1 1 -1 0 1 Output: 2
The final part of the definition says "one and only one path"
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.
Also, is a set of 1 point optimal?
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?