# 游耕者（夜）题解

## 解法比较

出题人解法做四次坐标变换与方向扫描：按横坐标排序，在以 $y-x$ 为索引的树状数组中维护最小 $x+y$ ，为每个点找所在扇区的候选近邻；重合点用零权边连接，再用 Kruskal 求曼哈顿最小生成树。递归 DFS 按首次访问顺序形成巡回。候选边交换论证和加倍树边后取捷径的证明均沿用出题人解法，见下文。

出题人实现把有界坐标平移后直接作为树状数组下标。Codex（GPT-6）采用的实现压缩实际出现的坐标，统一重合点处理，并用显式栈遍历。若直接坐标下标范围为 $U$ ，直接索引的时间为 $O(n\log(n+1)+n\log(U+1)+U)$ 、空间为 $O(n+U)$ ；Codex 实现为 $O(n\log(n+1))$ 时间、$O(n)$ 空间。优势是工作区不依赖坐标跨度，并避免深递归；方向筛边与巡回构造的证明适用于两种坐标表示。

## 从最小生成树构造巡回路线

把农场作为顶点，两点之间的距离作为无向边权。题面定义的最小连接成本 $M$ 正是这个完全图的最小生成树权值：任何连通图都能删除环上的边，得到权值不增的生成树。

求出一棵最小生成树 $T$ ，以农场 $1$ 为根做深度优先遍历，只在首次到达顶点时将它加入序列，最后补上 $1$ .实际实现使用显式栈，避免长链上的递归栈溢出。

### 为什么总代价不超过两倍

沿树边往返的完整遍历把每条边走两次，总代价恰为 $2M$ .从这个行走序列中跳过已经访问过的顶点，保留首次访问顺序和最终返回起点。由三角不等式，用一条直达边替换一段路径不会增加代价，所以得到的巡回路线满足：

$$C\le2M$$

![边长为 10 的正方形中，三条边构成权值 30 的树；按首次访问顺序闭合后，巡回长度为 40](assets/tree-tour.svg)

图中左侧树的完整往返顺序为 $1,2,3,4,3,2,1$ ，代价为 $60$ .跳过重复访问后得到右侧的 $1,2,3,4,1$ ，代价为 $40$ .

若最优巡回长度为 $OPT$ ，从最优回路中删去一条边便得到生成树，因此 $M\le OPT$ .参考构造满足 $C\le2OPT$ .题面为评测保留的容差允许 $C\le2.001M+0.001$ ，因此不能把所有获接受路线都宣称为严格的 2 倍近似。

## 重合点和边界

按坐标排序，将同坐标的农场保留一个代表，其余编号用零权边连接到代表。仅对互不相同的坐标求树，再加入这些零权边。它们不改变 $M$ ，并保证每个原始编号都出现在最终巡回中。

单个农场输出 `1 1` ；全部农场重合时 $M=C=0$ .不假设点处于一般位置，也不以随机扰动改变坐标或边权。

## 曼哈顿距离与三角不等式

横、纵坐标的绝对差分别满足三角不等式，将两式相加便得到 $d(a,c)\le d(a,b)+d(b,c)$ .因此前述跳过重复访问的构造适用。

## 用方向扫描求曼哈顿最小生成树

不能显式建立完全图。曼哈顿 MST 的方向筛边性质允许对每个点只保留各个 $45^\circ$ 区域中的一个最近邻，由这些线性数量的边求出一棵 MST。同一区域中两点之间的距离不会大于它们到区域顶点的较大距离，因此可通过树边交换排除不必要的远邻。并列距离可选择确定的最近邻；实现也覆盖区域边界。

边是无向的，只需覆盖朝向右半平面的四个区域。考虑其中满足下式的区域：

$$x_j\ge x_i,\qquad y_j-x_j\ge y_i-x_i$$

这也保证 $y_j\ge y_i$ ，因此两点之间的距离为：

$$d(i,j)=(x_j+y_j)-(x_i+y_i)$$

固定 $i$ 后，只需在满足上述条件的点中找 $x_j+y_j$ 最小的点。

1. 按横坐标降序、纵坐标降序扫描，已经处理的点满足横坐标条件；同横坐标的点按纵坐标降序处理。
2. 将所有 $y-x$ 离散化并反向编号。用树状数组维护每个前缀中 $x+y$ 最小的点；相等时按原编号确定顺序。
3. 查询当前 $y_i-x_i$ 对应的后缀，得到最近邻并加入候选边，然后插入当前点。
4. 对坐标变换 $(x,y)$ 、$(y,x)$ 、$(-y,x)$ 、$(x,-y)$ 分别做一次扫描，覆盖右上和右下的四个区域。无向边同时覆盖反方向。
5. 对至多线性数量的候选边排序，使用 Kruskal，并合并重合农场之间的零权边。

离散化使树状数组大小只与不同坐标的数量有关，不依赖坐标值域。每轮排序、查询和插入均为 $O(n\log n)$ ，四轮仍为 $O(n\log n)$ .

## 整数与实现细节

方向扫描中的坐标变换保持曼哈顿距离不变。候选边的权值用变换后的坐标和之差计算，但端点一直保存原农场编号。

本题一条边的代价不超过 $40000$ ，总路线长度以及评测中乘以 $1000$ 或 $2001$ 的结果使用有符号 64 位整数。所有距离和判定均为整数运算。

## 复杂度

设农场数为 $n$ .去重、候选边生成及 Kruskal 共需 $O(n\log(n+1))$ 时间，树遍历需 $O(n)$ 时间；总空间为 $O(n)$ .使用 $\log(n+1)$ 兼顾单点情形。完整图 Prim 对照程序需 $O(n^2)$ 时间和 $O(n)$ 空间，仅用于小规模验证。

## 特殊评测与复现

由于 $C,M$ 都是整数，精确使用以下等价条件：

$$1000C\le2001M+1$$

评测器检查恰有 $n+1$ 个整数、首尾为 $1$ 、前 $n$ 个编号组成排列，并逐边重算 $C$ .随后从输入重新计算 $M$ ，不读取参考路线的首个编号作为长度，也不把参考路线长度当作最优值。参考输出文件只为统一接口而要求存在，其内容不参与判定。

编译时保留题目目录内的 `mst.hpp` .标准程序与评测器共享这份经过独立对拍的实现；标准程序的输出只有巡回序列。

```text
g++ -std=c++17 -O2 std.cpp -o std
g++ -std=c++17 -O2 tests/checker.cpp -o checker
g++ -std=c++17 -O2 brute.cpp -o brute
g++ -std=c++17 -O2 tests/mst_weight.cpp -o mst_weight
python tests/generate.py --out-dir ../../../build/data/nomadism-night --std ./std
checker input.in reference.out contestant.out
```

`checker` 的退出码为：`0` 通过、`1` 答案错误、`2` 调用或输入材料错误。完整重新计算 $M$ 的开销属于检查器，部署时应为它设置足够的时间和内存。`brute.cpp` 是独立的完全图 Prim，只输出 $M$ ；`tests/mst_weight.cpp` 是诊断工具，输出 $M$ 及所选树的平方边长和，两者都支持连续读取多份输入到文件末尾。

正式数据使用固定 SplitMix64 种子，覆盖随机点、规则网格、窄条、等横坐标、共线、共圆、重合点、远隔点簇和最大规模。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。