P15821 [JOI Open 2013] 选票价值差 / Vote-Value Disparity

**这是一个提交答案题。** JOI 王国即将举行全国选举。JOI 王国由 $N$ 个省份组成。 JOI 王国的地图是一个大小为 $H \times W$ 的矩形网格。竖直方向有 $H$ 个格子，水平方向有 $W$ 个格子。一个格子通过其上、下、左、右四条边中的一条与另一个格子相连。这 $H \times W$ 个格子被划分为 $N$ 个省份。每个省份都是由格子组成的**连通区域**。第 $i$ 个省份（$1 \le i \le N$）总共有 $P_i$ 名选民。 你是 JOI 全国选举委员会的主席。你的任务是将这 $N$ 个省份划分为 $K$ 个选区（$1 \le K \le N$），以便选出 $K$ 名代表。每个选区必须至少包含一个省份，并且属于同一个选区的所有格子需要构成一个**连通区域**。注意，格子只能通过共享一条边（上、下、左、右）来连通，仅共享一个顶点（对角相邻）的格子不算连通。 对于每个选区，比值 $1 /$（该选区的选民总数）被称为该选区的**单票权重**。**选票价值差异**定义为所有选区的最大单票权重除以最小单票权重。 最近，“选票价值差异”的数值成为了一个严重的社会问题。你的任务是尽可能地让这个值变小。 ### 任务 给定 JOI 王国各省的信息以及代表人数，请确定如何将省份划分为选区，使得选票价值差异尽可能小。

从标准输入读取以下数据。 - 输入的第一行包含四个以空格分隔的整数 $H, W, N, K$。其中，JOI 王国地图的高度为 $H$，宽度为 $W$，省份数量为 $N$，代表人数为 $K$。 - 接下来的 $H$ 行中，每行包含 $W$ 个以空格分隔的整数。在第 $i$ 行（$1 \le i \le H$）中，第 $j$ 个整数（$1 \le j \le W$）为 $S_{ij}$（$1 \le S_{ij} \le N$）。这表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子属于第 $S_{ij}$ 个省份。 - 在接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $P_i$，表示第 $i$ 个省份的选民人数。

在 $N$ 行中输出将省份划分为选区的方式。输出的第 $i$ 行（$1 \le i \le N$）应包含一个整数，表示第 $i$ 个省份所属的选区编号。

### 样例 1 解释 在此样例中，JOI 王国的形状如下图所示。 :::align{center}  ::: 各省的选民人数分别为 3、5、7、10。在该样例输出中，省份被划分为以下选区： - 选区 1：省份 1 和省份 3 - 选区 2：省份 2 - 选区 3：省份 4 各选区的选民人数分别为 10、5、10。各选区的单票权重分别为 0.1、0.2、0.1。因此，选票价值差异为 $0.2 / 0.1 = 2$。如果 $X = 1.5$，$Y = 3$，则有 $\left(\frac{3 - 2}{3 - 1.5}\right)^2 \times 20 = 8.8\cdots$，该输出将获得 8 分。 对于此样例输入，以下划分是不允许的，因为选区 2 未能形成一个连通区域： - 选区 1：省份 1 - 选区 2：省份 2 和省份 4 - 选区 3：省份 3 ### 约束条件 所有输入数据满足以下条件。 - $1 \le H \le 200$ - $1 \le W \le 200$ - $1 \le N \le 10000$ - $1 \le K \le N$ - $1 \le P_i \le 100000$（$1 \le i \le N$） - 对于每个省份，属于该省份的所有格子构成一个连通区域。 ### 评分细则 对于每个输入文件，你的得分计算方式如下： 如果你的输出不满足题目描述中的条件，则得分为 0。如果满足条件，设 $D$ 为你输出方案的选票价值差异。那么你的得分按以下方式计算： - 如果 $Y < D$，得分为 0。 - 如果 $X < D \le Y$，得分为 $\left(\frac{Y - D}{Y - X}\right)^2 \times 20$ 的值**向下取整**。 - 如果 $D \le X$，得分为 20。 $X, Y$ 的取值如下表所示： | 输入文件 | X | Y | | :------: | :----: | :-: | | 01.txt | 1.02 | 2 | | 02.txt | 1.66 | 2.5 | | 03.txt | 1.06 | 2.5 | | 04.txt | 1.005 | 3 | | 05.txt | 1.0005 | 2 | 翻译由 DeepSeek V3.2 完成