285. [NOI 1999]最优连通子集

【题目描述】

众所周知，我们可以通过直角坐标系把平面上的任何一个点 $P$ 用一个有序数对 $(x,y)$ 来唯一表示，如果 $x,y$ 都是整数，我们就把点 $P$ 称为整点，否则点 $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,…,P_n}(n \geq 1)$，其中$P_i(1 \leq i \leq n)$属于 $W$，我们把 $S$ 称为整点集。

定义$3：$

  设 $S$ 是一个整点集，若点 $R,T$ 属于 $S$，且存在一个有限的点序列：$Q_1,Q_2,…,Q_k$ 满足:

      $1、Q_i$属于$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_{i+1}$

  我们则称点 $R$ 与点 $T$ 在整点集 $S$ 上连通，把点序列 $Q_1,Q_2,…,Q_k$ 称为整点集 $S$ 中连接点 $R$ 与点 $T$ 的一条道路。

定义$4：$

  若整点集 $V$ 满足：对于 $V$ 中的任何两个整点，$V$ 中有且仅有一条连接这两点的道路，则 $V$ 称为单整点集。

定义$5：$

  对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。

我们希望对于给定的一个单整点集 $V$，求出一个 $V$ 的最优连通子集 $B$，满足：

  $1、B$ 是 $V$ 的子集；

  $2、$对于 $B$ 中的任何两个整点，在$B$中连通；

  $3、B$ 是满足条件 $(1)$ 和 $(2)$ 的所有整点集中权和最大的。

【输入格式】

第 $1$ 行是一个整数 $N$，表示单整点集 $V$ 中点的个数；

接下来 $N$ 行中，第 $i$ 行($1 \leq i \leq N$)有三个整数，$X_i,Y_i,C_i$ 依次表示第 $i$ 个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。

【输出格式】

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

【样例输入1】

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

【样例输出1】

2

【输入/输出样例2】

输入输出样例2 

【数据规模与约定】

$100$%的数据，$2 \leq N \leq 1000$，$-10^6 \leq X_i,Y_i \leq 10^6$，$-100 \leq C_i \leq 100$;

【来源】

$NOI$ $1999$