P1433 吃奶酪 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1433，日期见页头。两边不一致时信原站。

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？ 老鼠一开始在 (0,0) 点处。

输入格式

第一行有一个整数，表示奶酪的数量 n。

第 2 到第 (n + 1) 行，每行两个实数，第 (i + 1) 行的实数分别表示第 i 块奶酪的横纵坐标 xᵢ, yᵢ。

输出格式

输出一行一个实数，表示要跑的最少距离，保留 2 位小数。

说明/提示

数据规模与约定

对于全部的测试点，保证 1 ≤ n ≤ 15，|xᵢ|, |yᵢ| ≤ 200，小数点后最多有 3 位数字。

提示

对于两个点 (x₁, y₁)、(x₂, y₂)，两点之间的距离公式为 √((x₁−x₂)² + (y₁−y₂)²)。

2022.7.13：新增加一组 Hack 数据。

输入输出样例

输入

输出

7.41

四块奶酪在四个角上。从 (0,0) 出发，√2 + 2 + √2 + 2 ≈ 7.41。

⚠ 这一组样例只挡住了三个错法里的一个（「多加了回起点」打出 8.83）—— 而贪心和 float 版都原样打出 7.41。

1★★★ 先看清楚它和上一道题差在哪 —— 就一句话

★ 「不用回来」——而这正是 [P1171] 那一页里的 bug

同题单的 P1171 售货员是闭合式 TSP：走遍所有村庄，还要回商店。这道题是开放式：老鼠吃完最后一块就收工。

    P1171   答案 = min over i of f[全集][i] + d[i][起点]
    P1433   答案 = min over i of f[全集][i]              ← 少的就是这一段

⇒ ★★★ 同一段代码，在那道题上是错法（p1171NoBack.cpp），在这道题上是正解。

⚠ 所以「上一道题怎么写」不能当默认值。两道题挨着放在同一张题单里， 恰恰是因为它们不一样 —— 这是第 27 章那条「编号基在同一张题单里会翻面」的升级版：这次翻面的不是格式，是题目要求本身。

p1433Back.cpp✗ 把 P1171 的模板原样搬来（多加了回起点）

// ✗ P1433：加回了起点那一段（把 [P1171 售货员] 的模板原样搬过来）
//
// ★ 它解的是**闭合式 TSP**（吃完还要跑回 (0,0)）—— 题面没这个要求。
//    多了一条必须走的边 ⇒ 它解的是一个**收紧了的问题** ⇒ 它的答案**恒 ≥ 正解**。
// ⇒ ★★ 和 [P1171](/sol/p1171/) 那一页的「忘了加回起点」正好互为镜像：
//    同一处差别，在那道题上是「少加了」，在这道题上是「多加了」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) { printf("0.00\n"); return 0; }
    vector<double> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    auto dis = [&](double ax, double ay, double bx, double by) {
        return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
    };
    int full = (1 << n) - 1;
    vector<vector<double>> f(1 << n, vector<double>(n, 1e18));
    for (int i = 0; i < n; i++) f[1 << i][i] = dis(0, 0, x[i], y[i]);
    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || f[S][i] >= 1e17) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                double& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + dis(x[i], y[i], x[j], y[j]));
            }
        }
    double ans = 1e18;
    for (int i = 0; i < n; i++) ans = min(ans, f[full][i] + dis(x[i], y[i], 0, 0));   // ← 多加了
    printf("%.2f\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

它多了一条必须走的边 ⇒ 解的是一个收紧了的问题 ⇒ 恒 ≥ 正解（300 / 300），被抓 300 / 300，平均多跑 21.09%。★ 官方样例当场挡住它（8.83 vs 7.41）。

2★ 正解：状压 DP，起点不占状态位

p1433.cpp★ 这一版就能 AC

// P1433 吃奶酪 —— 正解：状压 DP（**开放式** TSP），O(2ⁿ × n²)
//
//   f[S][i] = 已经吃掉的奶酪集合是 S（且 i ∈ S），此刻老鼠停在第 i 块奶酪处，
//             从 (0,0) 出发跑过的最短距离。
//   答案 = min over i of f[全集][i]        ★ **不用回起点** —— 这就是它和 [P1171] 的全部差别
//
// ⚠⚠ 而这一句正是 [P1171](/sol/p1171/) 那一页里的 **bug**（那道题要回商店）。
//    ⇒ **同一段代码，两道题一个是错法、一个是正解。**
//
// ★ 起点 (0,0) 不占状态位：它不是「一块奶酪」，所以初值直接写
//      f[1<<i][i] = dist(起点, i)
// ⚠ 草稿这儿原来写着「否则会白白多一倍**状态**」—— 实测把它分成了两句：
//   **转移次数几乎一样**（n = 12 时 135168 vs 135180，差 1.00 倍 —— 多出来的那些状态
//   根本到不了，内层的可达性判断当场就把它们跳过了），
//   **而数组真的大一倍多**（n = 15 的 double 表 3840 KB → 8192 KB，2.13 倍）。
//   ⇒ 又一次「换尺子结论不同」：这一次「省下来的」是内存，不是时间。
//
// ⚠ 距离是浮点数 ⇒ **对拍不能逐字节比**，只能按容差（见 p1433Count.cpp 第 ⑤ 段）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) { printf("0.00\n"); return 0; }
    vector<double> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    auto dis = [&](double ax, double ay, double bx, double by) {
        return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
    };

    int full = (1 << n) - 1;
    vector<vector<double>> f(1 << n, vector<double>(n, 1e18));
    for (int i = 0; i < n; i++) f[1 << i][i] = dis(0, 0, x[i], y[i]);   // ★ 起点不占状态位

    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || f[S][i] >= 1e17) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                double& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + dis(x[i], y[i], x[j], y[j]));
            }
        }

    double ans = 1e18;
    for (int i = 0; i < n; i++) ans = min(ans, f[full][i]);   // ★ 不回起点
    printf("%.2f\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

⚠ 「起点要不要也编进集合」—— 两把尺子结论不同

起点 (0,0) 不是一块奶酪，所以初值直接写 f[1<<i][i] = dist(起点, i)，集合里只装奶酪。另一种写法是把起点当成第 0 个元素，状态位多一位。

草稿里我写的是「那会白白多一倍状态」。实测把这句话拆成了两半：

	起点不占位	起点也编进去	差
转移次数（`n = 12`）	135 168	135 180	★ 1.00 倍（几乎一样）
`double` 表（`n = 15`）	3 840 KB	8 192 KB	★ 2.13 倍

次数几乎一样，因为多出来的那些状态（不含起点位的）根本到不了，内层那句可达性判断当场就跳过了；而数组是实打实大了一倍多。

⇒ ★★ 又一次「换一把尺子结论就不同」（P1074 那条）—— 这一次省下来的是内存，不是时间。 ★ 两种写法答案一致 300 / 300 轮，所以这不是对错问题，是选哪个的问题。

3★★ 最近邻贪心：同一个贪心，换个距离就温和多了

p1433Greedy.cpp✗ 每次跑去最近的那块

// ✗ P1433 第一版：每次跑去最近的那块奶酪（最近邻贪心）
//
// ★ 它给出的是一条**真跑得出来的路线** ⇒ 它的距离**恒 ≥ 最优**。
// ⚠ 而这道题的坐标是欧氏距离（满足三角不等式），比 [P1171](/sol/p1171/) 那种
//    随机有向边「温和」得多 —— 所以**同一个贪心在这道题上错得轻**，这一页量了差多少。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) { printf("0.00\n"); return 0; }
    vector<double> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    auto dis = [&](double ax, double ay, double bx, double by) {
        return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
    };
    vector<char> vis(n, 0);
    double cx = 0, cy = 0, sum = 0;
    for (int t = 0; t < n; t++) {
        int best = -1;
        for (int j = 0; j < n; j++)
            if (!vis[j] && (best < 0 || dis(cx, cy, x[j], y[j]) < dis(cx, cy, x[best], y[best]))) best = j;
        sum += dis(cx, cy, x[best], y[best]);
        vis[best] = 1;
        cx = x[best]; cy = y[best];
    }
    printf("%.2f\n", sum);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 和 P1171 并排看 —— 「这个贪心有多差」的主语是距离长什么样

	P1171（随机有向边）	P1433（欧氏距离）
恒 ≥ 正解	300 / 300	300 / 300
300 轮被抓	285	239
错时平均多跑	★ 56.40%	★ 10.15%
最多多跑	182.38%	37.45%

⇒ 同一份贪心、同一个 n，错的幅度差 5.6 倍。 原因是欧氏距离满足三角不等式（绕远路一定更贵），而 P1171 那种随机有向边什么结构都没有 —— 贪心可以被坑到极惨。

⚠ 而形状这把旋钮还能再拧：把奶酪全撒在一条直线上，贪心被抓 197 / 300 （对照默认档 239）—— 更规整的数据反而更难抓。

4⚠⚠ 第三个错法：float —— 草稿说它必挂，实测 300 轮只错 1 轮

p1433Float.cpp⚠ 用 float 存距离

// ✗ P1433：用 float 存距离
//
// ⚠⚠ 草稿里我把它当成一个「肯定会出事」的错法（float 只有约 7 位有效数字，
//    而总距离能到四位数）。**实测把这句话按回去了：300 轮只错 1 轮。**
//
// 真正的量是这样的：float 版和 double 版的**最大绝对偏差只有 0.000143**
// （顶格 n = 15 是 0.000164），而答案只要**两位小数** ——
// 所以它只在「真值恰好压在 x.xx5 的分界上」时才会翻过去。
// ⇒ 实测：被抓 **1 / 300**，而「答案离那条分界不到 2e-4」的轮数是 **19** —— 触发条件差 19 倍。
//
// ★★ 结论不是「float 能用」，是**「它错得很稀有」这件事本身才是危险的**：
//    交上去多半过，偶尔挂一个点，而你完全看不出为什么。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) { printf("0.00\n"); return 0; }
    vector<float> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    auto dis = [&](float ax, float ay, float bx, float by) {
        return sqrtf((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
    };
    int full = (1 << n) - 1;
    vector<vector<float>> f(1 << n, vector<float>(n, 1e18f));
    for (int i = 0; i < n; i++) f[1 << i][i] = dis(0, 0, x[i], y[i]);
    for (int S = 0; S <= full; S++)
        for (int i = 0; i < n; i++) {
            if (!(S >> i & 1) || f[S][i] >= 1e17f) continue;
            for (int j = 0; j < n; j++) {
                if (S >> j & 1) continue;
                float& t = f[S | 1 << j][j];
                t = min(t, f[S][i] + dis(x[i], y[i], x[j], y[j]));
            }
        }
    float ans = 1e18f;
    for (int i = 0; i < n; i++) ans = min(ans, f[full][i]);
    printf("%.2f\n", ans);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 「它会错」和「它多久错一次」是两个问题，而后者才决定你会不会被坑

草稿里我把它当成一个「肯定出事」的错法：float 只有约 7 位有效数字，而总距离能到四位数。 实测把这句话按了回去：


300 轮里打印结果和 `double` 不同	★ 1 / 300
最大绝对偏差	★ 0.000143
顶格 `n = 15`（60 轮）	0 轮不同，最大偏差 0.000164
⚠ 而「答案离两位小数的分界不到 `2e-4`」的轮数	19

偏差只有万分之一，而答案只要两位小数 ⇒ 它只在「真值恰好压在 x.xx5 那条线上」时才翻过去。触发条件 19 轮、真被抓 1 轮 —— 又一次「触发条件 ≠ 抓获率」（本书量到的第八次，差 19 倍）。

⇒ ★★ 结论不是「float 能用」，恰恰相反： 「它错得很稀有」这件事本身才是危险的 —— 交上去多半过，偶尔挂一个点，而你从输出上完全看不出为什么。

5★★★ 实数题的对拍：逐字节 vs 容差

★ 这道题上两种口径给出了同一个答案 —— 但那是这道题的运气

正解 vs 暴力，300 轮
容差口径（`	a−b
逐字节口径（比 `%.2f` 打出来的字符串）	0 轮不同

这道题上两种口径一致，因为正解和暴力算的是同一批浮点加法、顺序也基本相同。

⚠ 但第 19 章 P2240 那一页量过反例：那道题里「精确值四舍五入」和 printf("%.2f") 有 0.93% 的输入打出不同的字符串。 ⇒ ★★ 实数题的默认口径是容差；逐字节比只有在你确认过两版的浮点路径一致时才安全，而那句「确认过」得像上面这样跑出来。

p1433Brute.cpp参照物：n! 全排列（300 轮容差不一致 0 轮）

6度量程序和生成器

⚠ 生成器有个容易漏的点：题面写着坐标小数点后最多 3 位，而顺手写的生成器多半只会撒整数坐标 —— 那样就永远测不到「小数怎么读进来」这件事。 ⇒ 本页的生成器默认档带三位小数，档位 1 才是整数（留着对照用）。

p1433Count.cpp度量程序（本页所有数字都出自它）

p1433Gen.cpp数据生成器

7一页纸


★★★ 和上一道的全部差别	不用回起点 —— 而那一句正是 P1171 那页的 bug
★ 多加了回起点	收紧了的问题 ⇒ 恒 ≥ 正解，被抓 300/300，平均多跑 21.09%（样例挡住）
★★ 最近邻贪心	恒 ≥ 正解，被抓 239/300，错时平均多跑 10.15% —— 对照 P1171 的 56.40%，差 5.6 倍
⚠⚠ `float`	草稿说必挂，实测 300 轮只错 1 轮（最大偏差 0.000143）⇒ 稀有才更危险
⚠ 起点占不占状态位	转移次数差 1.00 倍、数组差 2.13 倍 —— 换尺子结论不同，省的是内存
★★ 实数对拍	这道题上容差和逐字节都是 0 轮不同；⚠ 但默认口径仍是容差（P2240 有反例）
参照物	`n!` 全排列（不回起点）；300 轮不一致 0 轮

洛谷 P1433 吃奶酪

0题目原文（本地存了一份）

数据规模与约定

提示

输入

输出

1★★★ 先看清楚它和上一道题差在哪 —— 就一句话

2★ 正解：状压 DP，起点不占状态位

3★★ 最近邻贪心：同一个贪心，换个距离就温和多了

4⚠⚠ 第三个错法：float —— 草稿说它必挂，实测 300 轮只错 1 轮

5★★★ 实数题的对拍：逐字节 vs 容差

6度量程序和生成器

7一页纸