题目描述

在平面直角坐标系中，如果一个点$P$的坐标$(x, y)$均为整数，则称$P$为整点。所有整点的集合记为$W$。

定义1

对于两个整点$P_1(x_1, y_1)$和$P_2(x_2, y_2)$，如果$|x_1 - x_2| + |y_1 - y_2| = 1$，则称$P_1$和$P_2$相邻，记作$P_1 \sim P_2$；否则称$P_1$和$P_2$不相邻。

定义2

设$S$是$W$的一个有限子集，即$S = \{P_1, P_2, \dots, P_n\}$（$n \geq 1$），其中每个$P_i$（$1 \leq i \leq n$）属于$W$，则称$S$为一个整点集。

定义3

设$S$是一个整点集，如果点$R, T \in S$，并且存在一个有限的点序列$Q_1, Q_2, \dots, Q_k$满足：

1. $Q_i \in S$（$1 \leq i \leq k$）；
2. $Q_1 = R$，$Q_k = T$；
3. $Q_i \sim Q_{i+1}$（$1 \leq i \leq k-1$），即$Q_i$与$Q_{i+1}$相邻；
4. 对于任意$1 \leq i < j \leq k$，有$Q_i \neq Q_j$；

则称$R$与$T$在$S$上连通，并将点序列$Q_1, Q_2, \dots, Q_k$称为$S$中连接$R$和$T$的一条道路。

定义4

如果一个整点集$V$满足：对于$V$中的任意两个整点，$V$中有且仅有一条连接它们的道路，则称$V$为单整点集。

定义5

对于平面上的每个整点，可以赋予它一个整数作为该点的权值。整点集$S$中所有点的权值之和称为$S$的权和。

问题描述

给定一个单整点集$V$，求$V$的一个最优连通子集$B$，满足：

1. $B \subseteq V$；
2. 对于$B$中的任意两个整点，它们在$B$中连通；
3. $B$是所有满足条件（1）和（2）的整点集中权和最大的。

输入格式

• 第1行是一个整数$N$（$2 \leq N \leq 1000$），表示单整点集$V$中点的个数；
• 接下来的$N$行，每行包含三个整数$X_i, Y_i, C_i$，分别表示第$i$个点的横坐标、纵坐标和权值。同一行相邻两数之间用空格分隔。
  坐标范围：$-10^6 \leq X_i, Y_i \leq 10^6$；
  权值范围：$-100 \leq C_i \leq 100$。

输出格式

• 仅一个整数，表示所求最优连通子集的权和。

示例输入

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

示例输出

2

题目来源

Noi 99