SP1453 OPTSUB - Optimal Connected Subset

- 当一个点 \( P(x, y) \) 的横坐标 \( x \) 和纵坐标 \( y \) 都是整数时，称其为整点。 - \( W \) 是平面上所有整点的集合。 - 如果两个整点 \( P(x, y) \) 和 \( Q(x', y') \) 满足 \( |x - x'| + |y - y'| = 1 \)，则称它们是相邻的。 - \( S \) 是整点的一个集合，当且仅当 \( S \) 是 \( W \) 的有限子集。 - 如果 \( S \) 是整点集合，而 \( R \) 和 \( T \) 都属于 \( S \)，并且存在一个有限的整点序列 \( Q_0 = R, Q_1, Q_2, \ldots, Q_k, Q_{k+1} = T \) 满足： - 序列中的各个点 \( Q_i \) 都不相同，即 \( i \neq j \) 时 \( Q_i \neq Q_j \)。 - 对于每一个 \( 0 \leq i \leq k \)，\( Q_i \) 和 \( Q_{i+1} \) 是相邻的。 - 对于每一个 \( 0 \leq i \leq k+1 \)，\( Q_i \) 都在集合 \( S \) 中。

第一行输入一个整数 \( T \)，表示测试用例的数量。接下来是 \( T \) 个测试用例。 每个测试用例的第一行是一个整数 \( N = |V| \)（\( N \leq 1000 \)），表示整点的数量。接下来的 \( N \) 行中，每行有三个整数，分别表示第 \( i \) 个整点的 \( X \) 坐标、\( Y \) 坐标和权重（权重的绝对值不超过 100），这些整数之间用空格分隔。

输出共 \( T \) 行，每行一个整数，表示对于每个测试用例中权重的最大和。 **本翻译由 AI 自动生成**