P5766 [NOI1999] 最优联通子集

众所周知，我们可以通过直角坐标系把平面上的任何一个点 $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$~$P_2$ ，否则称 $P_1,P_2$ 不相邻。 定义 2 ：设点集 $S$ 是 $W$ 的一个有限子集，即 $S$=$\{P_1,P_2,…,P_n\}$ $(n \ge 1)$，其中 $P_i (1 \le i \le n)$ 属于 $W$，我们把 $S$ 称为整点集。 定义 3 ：设 $S$ 是一个整点集，若点 $R$,$T$ 属于 $S$ ，且存在一个有限的点序列 $Q_1,Q_2,…,Q_k$ 满足: 1. $Q_i$ 属于 $S$ （$ 1 \le i \le k $）; 2. $Q_1$ = $R$,$Q_k$ = $T$; 3. $Q_i$~$Q_{i+1} (1 \le i \le k-1)$，即 $Q_i$ 与 $Q_{i+1}$ 相邻; 4. 对于任何 $1 \le i

无

无