AT_ahc045_a [AHC045A] Oracle-Guided Road Network Planning
题目背景
昔々、高橋王国にはたくさんの都市が点在していましたが、道路が無く人々は都市間の移動に苦労していました。 そこで国王の高橋くんは、都市をいくつかのグループに分け、グループ内の任意の2都市間が道路によって互いに行き来できるように都市を結ぶ道路を建設することで、国を発展させる計画を考えました。 高橋くんはなるべく建設する道路の総長を短くしたいと考えていましたが、高橋王国には正確な地図が無く、各都市の位置がはっきりしていないという問題がありました。
どのように道路を建設するべきか困った高橋くんは、王国一の占い師に助けを求めることにしました。 占い師は、いくつかの都市を選ぶことで、それらの都市同士を互いに行き来できるような総長の最も短い道路の建設方法を知ることができます。 ただし、占いの回数には限界があります。
なるべく建設する道路の総長を短くできるように、最適な占い方および道路の建設計画を考えてください。
题目描述
平面上有 $N$ 个城市，编号为 $0$ 到 $N-1$。城市 $i$ 的坐标为 $(x_i, y_i)$，该坐标在评测系统内部已确定，但不会在输入中给出。取而代之，输入会给出城市 $i$ 可能存在的矩形区域范围 $lx_i, rx_i, ly_i, ry_i$，满足 $lx_i \le x_i \le rx_i$ 且 $ly_i \le y_i \le ry_i$。
城市间的距离定义为欧几里得距离向下取整后的整数值，即 $\mathrm{dist}(i, j) = \left\lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \right\rfloor$。
给定一个长度为 $M$ 的数组 $G$。请将所有城市分成 $M$ 个组，每组的城市数量分别为 $G_0, G_1, \dots, G_{M-1}$，并在每组内修建道路，使得同组内的城市连通。
在输出答案之前，你可以最多进行 $Q$ 次如下形式的“占卜”查询：
- 选择城市集合 $C \subset \{0, 1, \cdots, N-1\}$，其大小 $l = |C|$ 满足 $2 \le l \le L$，其中 $L$ 为输入给定的上限。
- 对于该查询，你将获得在城市集合 $C$ 上构建最小生成树所需的 $l-1$ 条道路，每条道路连接的城市对。最小生成树的构建方式如下：
- 边集 $E$ 初始化为 $C$ 内任意两城市之间的边。
- 按照城市间真实距离升序对 $E$ 排序。若距离相等，则按城市编号对 $(u, v)$（$u < v$）升序排序。
- 依次从 $E$ 中取出边，若加入该边不会成环，则将其加入最小生成树。
- 最小生成树中的每条边，按 $(u, v)$（$u < v$）升序排序后作为查询的响应。
之后，请输出满足以下条件的城市分组和道路建设方案：
- 将 $N$ 个城市分为 $M$ 个组，每组 $i$ 分配 $G_i$ 个城市。每个城市必须且仅能属于一个组。
- 对于每组 $i$，选择 $G_i-1$ 条道路连接组内城市，使得组内任意两城市间通过道路可达，即组内连通。
- 每条道路仅连接其两端的城市。即使多条道路在平面上交叉，也不能从一条道路转到另一条道路。
输入格式
首先输入城市数量 $N$，分组数量 $M$，最大查询次数 $Q$，查询集合最大大小 $L$，矩形最大宽高 $W$，各组城市数量 $G_0, G_1, \cdots, G_{M-1}$，以及每个城市的可能坐标范围 $lx_i, rx_i, ly_i, ry_i$，格式如下：
> $N$ $M$ $Q$ $L$ $W$ $G_0$ $G_1$ $\cdots$ $G_{M-1}$
> $lx_0$ $rx_0$ $ly_0$ $ry_0$
> $\vdots$
> $lx_{N-1}$ $rx_{N-1}$ $ly_{N-1}$ $ry_{N-1}$
各数值满足以下约束：
- $N = 800$
- $1 \leq M \leq 400$
- $Q = 400$
- $3 \leq L \leq 15$
- $500 \leq W \leq 2500$
- $1 \leq G_i \leq N$
- $\sum_{i=0}^{M-1} G_i = N$
- $0 \leq lx_i \leq rx_i \leq 10000$
- $0 \leq rx_i - lx_i \leq W$
- $0 \leq ly_i \leq ry_i \leq 10000$
- $0 \leq ry_i - ly_i \leq W$
- 输入均为整数。
在读取上述信息后，你可以最多进行 $Q$ 次查询。
每次查询，选择城市集合 $C \subset \{0, 1, \cdots, N-1\}$，其大小 $l = |C|$ 满足 $2 \leq l \leq L$。以如下格式输出一行：
> ? $l$ $C_0$ $C_1$ $\cdots$ $C_{l-1}$
**每次输出后必须换行，并刷新标准输出，否则可能会TLE。**
输出后，将从标准输入获得该集合 $C$ 上最小生成树的 $l-1$ 条边，每条边为 $a_i, b_i \in C$，格式如下：
> $a_0$ $b_0$
> $\vdots$
> $a_{l-2}$ $b_{l-2}$
完成最多 $Q$ 次查询后，首先输出一行仅包含符号 !：
> !
然后，对每个组输出如下内容，共 $M$ 组。对于第 $k$ 组，输出该组分配的城市集合 $C \subset \{0, 1, \cdots, N-1\}$，以及组内 $G_k-1$ 条道路，每条道路连接 $a_i, b_i \in C$，格式如下：
> $C_0$ $C_1$ $\cdots$ $C_{G_k-1}$
> $a_0$ $b_0$
> $\vdots$
> $a_{G_k-2}$ $b_{G_k-2}$
输出需满足以下约束：
- 每个城市必须且仅属于一个组。
- 每组内任意两城市通过道路可达，即组内连通。
输出格式
见上文输入格式说明。
说明/提示
### 故事背景
很久以前，高桥王国有许多城市分布在各地，但没有道路，人们在城市间的移动非常困难。于是国王高桥君决定将城市分组，并在每组内修建道路，使得组内任意两城市间可以互相到达，从而促进国家发展。但由于没有准确的地图，城市的具体位置并不清楚。
高桥君为此向王国最强的占卜师求助。占卜师可以选定一些城市，得知这些城市间连通所需的最短道路方案，但占卜次数有限。
请设计最优的占卜方式和道路建设方案，使得修建道路的总长度尽可能短。
### 得分
你输出的道路建设方案中所有道路的总长度为绝对分数。城市 $i$ 和城市 $j$ 之间的道路长度为 $\mathrm{dist}(i, j) = \left\lfloor \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \right\rfloor$，其中 $(x_i, y_i)$ 为真实坐标。**绝对分数越小越好。**
每个测试用例的相对分数为 $\mathrm{round}(10^9 \times \frac{\text{全体选手中该用例的最小绝对分数}}{\text{你的绝对分数}})$，所有用例的相对分数之和为你的总得分。
最终排名以赛后系统测试的得分为准。无论是暂定测试还是系统测试，若某些用例输出非法或超时，则该用例相对分数为0，并且不参与最小绝对分数的计算。系统测试只对**最后一次非CE提交**进行，请务必保证最终提交正确。
#### 测试用例数
- 暂定测试：50个
- 系统测试：3000个，赛后会公开 [seeds.txt](https://img.atcoder.jp/ahc045/seeds.txt) (sha256=e4cb8e03f20f6a97dd082c75ad60cc31447bd24b5b3ebe5e64af4ac28712b618)
#### 相对评分系统说明
无论暂定测试还是系统测试，只有最后一次非CE提交会计入排行榜。每个用例的全体选手最小绝对分数也只统计排行榜上的最后一次提交。
排行榜显示的是相对分数，每次新提交都会重新计算。提交列表中显示的是绝对分数之和，不显示相对分数。若想知道非最新提交的相对分数，需要重新提交。输出非法或超时时，提交列表分数为0，但排行榜会显示已通过用例的相对分数之和。
#### 执行时间说明
执行时间会有一定波动。系统测试时因并发执行较多，通常比暂定测试慢几个百分点。因此，建议程序中自行计时，或留有充足时间余量，避免系统测试TLE。
### 输入生成方法
用 $\mathrm{rand\_int}(L, U)$ 表示生成 $L$ 到 $U$ 间的整数，$\mathrm{rand\_double}(L, U)$ 表示生成 $L$ 到 $U$ 间的实数。
#### $M, L, W$ 的生成
- $M = \left\lfloor (\mathrm{rand\_double}(1.0, 20.0))^2 \right\rfloor$
- $L = \mathrm{rand\_int}(3, 15)$
- $W = \mathrm{rand\_int}(500, 2500)$
#### $G$ 的生成
- 从 $1$ 到 $N-1$ 间随机生成 $M-1$ 个不重复整数，升序排列为 $A_1, A_2, \cdots, A_{M-1}$。
- 设 $A_0 = 0, A_M = N$，则 $G_i = A_{i+1} - A_i$。
#### $x_i, y_i, lx_i, rx_i, ly_i, ry_i$ 的生成
- $x_i = \mathrm{rand\_int}(0, 10000)$
- $y_i = \mathrm{rand\_int}(0, 10000)$
- $w_i = \mathrm{rand\_int}(0, W)$
- $dx_i = \mathrm{rand\_int}(0, w_i)$
- $rx_i = x_i + dx_i$
- $lx_i = rx_i - w_i$
- $dy_i = \mathrm{rand\_int}(0, w_i)$
- $ry_i = y_i + dy_i$
- $ly_i = ry_i - w_i$
- 若 $lx_i, rx_i, ly_i, ry_i$ 超出 $[0, 10000]$，则截断到 $0$ 或 $10000$。
### 工具（输入生成器与可视化器）
- [网页版](https://img.atcoder.jp/ahc045/jOO09LxU.html?lang=ja)：功能强大，支持动画显示。
- [本地版](https://img.atcoder.jp/ahc045/jOO09LxU_v2.zip)：需安装 [Rust](https://www.rust-lang.org/ja)。
- [Windows编译版](https://img.atcoder.jp/ahc045/jOO09LxU_windows_v2.zip)：无需Rust环境。
**比赛期间禁止分享可视化结果、解法或思路。**
#### 工具输入输出文件说明
本地测试器输入文件在题面输入末尾追加如下内容：
> $x_0$ $y_0$
> $\vdots$
> $x_{N-1}$ $y_{N-1}$
$x_i, y_i$ 为城市 $i$ 的真实坐标，解答程序无法获得。
### 示例程序
Python 示例实现：
```python
def query(c):
print("?", len(c), *c, flush=True)
return [tuple(map(int, input().split())) for _ in range(len(c) - 1)]
def answer(groups, edges):
print("!")
for i in range(len(groups)):
print(*groups[i])
for e in edges[i]:
print(*e)
# read input
N, M, Q, L, W = map(int, input().split())
G = list(map(int, input().split()))
lx, rx, ly, ry = [], [], [], []
for _ in range(N):
a, b, c, d = map(int, input().split())
lx.append(a)
rx.append(b)
ly.append(c)
ry.append(d)
# use center of rectangle
x = [(l + r) // 2 for l, r in zip(lx, rx)]
y = [(l + r) // 2 for l, r in zip(ly, ry)]
# split cities into groups
cities = list(range(N))
cities.sort(key=lambda i: (x[i], y[i]))
groups = []
start_idx = 0
for g in G:
groups.append(cities[start_idx : start_idx + g])
start_idx += g
# get edges from queries
edges = []
for k in range(M):
edges.append([])
for i in range(0, G[k] - 1, 2):
if i
```
该程序实现了如下处理：
1. 用每个城市可能矩形的中心坐标 $(\frac{lx_i + rx_i}{2}, \frac{ly_i + ry_i}{2})$ 排序，并按此顺序分组。
2. 对每组，采用滑动窗口方式每次对3个城市进行查询，将查询返回的边直接作为答案。
3. 若某组最后一个城市未被查询，则将其与组内前一个城市直接连边。
# 输入格式
见上文。
# 输出格式
见上文。
# 提示
见上文。
由 ChatGPT 4.1 翻译