信息学奥赛算法练功房◌检测中
题单　·　习题解析

洛谷 P2872 [USACO07DEC] Building Roads S

★★ 关键一步全在**建图**：完全图 499 500 条边 ＋ 已修好的路权值当 0 ⇒ 剩下就是一句 MST；★★★ 最经典的一发 WA 是 `dx * dx` 用 int —— 分界线 **46 341**（`46340² < 2³¹ ≤ 46341²`，和 [P1516](/sol/p1516/) 一字不差），⚠ 而坐标压到 1000 的生成器让它变成**精确的 0**；★ 题面明写「请用 **64 位**实型」—— 答案量级 1.41 × 10⁹ 而 float 只有 7 位有效数字（⚠ 档 0 抓 **2** 次，不是 0）；★★★ 同一个「用平方代替距离」的念头**一半对一半错**：比较成立、求和不成立（`√a + √b ≠ √(a+b)`）；★★ 这道题 Prim 9 ms / Kruskal 39 ms ⇒ **4.3 倍**，而 [P1546](/sol/p1546/) 上同一句话一分不值 ⇒ 「稠密图用朴素 Prim」的主语是 n；★★★ **实数输出能不能逐字节比要量** —— 这道题 0 组不同，[P2240](/sol/p2240/) 是 0.93%；★★★ 四个错法的触发条件**全部 ≡ 抓获数，四档全对**

原题：洛谷 P2872出自 第 34 章 最小生成树：Kruskal 与 Prim 的题单题面本地存档：2026-08-31
⚠ 先自己写一遍，再往下看

这一页不是标准答案，是一条阶梯：把大多数人真实会写出的第一版摆出来， 看它错在哪、慢在哪，再一步一步改。所以它对「已经自己动手撞过一次墙」的人最有用。
还没写过的话，先去写 —— 写出来的哪怕是错的，也比直接看这一页收获大。

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

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

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

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

题目描述

给定 n 个点的坐标，第 i 个点的坐标为 (xᵢ, yᵢ)，这 n 个点编号为 1 到 n。给定 m 条边，第 i 条边连接第 uᵢ 个点和第 vᵢ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

第一行两个整数 n, m 代表点数与边数。

接下来 n 行每行两个整数 xᵢ, yᵢ 代表第 i 个点的坐标。

接下来 m 行每行两个整数 uᵢ, vᵢ 代表第 i 条边连接第 uᵢ 个点和第 vᵢ 个点。

输出格式

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差，请用 64 位实型变量进行计算。

说明/提示

对于 100% 的数据，1 ≤ n, m ≤ 1000，1 ≤ xᵢ, yᵢ ≤ 10⁶，1 ≤ uᵢ, vᵢ ≤ n。

时限 1 秒，内存 125 MB。

输入输出样例

输入

4 1
1 1
3 1
2 3
4 3
1 4

输出

4.00

四个点 (1,1) (3,1) (2,3) (4,3)，已经有一条 1-4 的路（白送）。 还差把 2 和 3 连进来：1-2 长 2、3-4 长 2 ⇒ 添加的总长 4.00。

1★★ 关键的一步全在建图 —— 算法只是最后一句

★★ 题面没给你一张图，它给了你一堆点
题面给的 翻成图是什么
n 个点的坐标 ★ 任意两点之间都可以修一条路 ⇒ 完全图，n(n−1)/2 = 499 500 条边
边长 欧几里得距离 √(dx² + dy²)
m 条已经修好的路 ★ 权值当 0 —— 它们不要钱，唯一的作用是先把两头连起来
「添加的边总长最小」 ⇒ 一句最小生成树

★ 这就是本章题单里那句「建图比算法难」的意思：想明白上面这张表之后， 剩下的就是本章第 7 步那份代码。

p2872.cpp★ 这一版就能 AC（朴素 Prim，顶格本机 9 毫秒）
// P2872 [USACO07DEC] Building Roads S —— ★ 这一版就能 AC
//
// ★★ 这道题**难的不是算法，是建图**（本章题单那句「建图比算法难」）：
//   题面只给了 n 个点的坐标和 m 条**已经修好**的路 ——
//   而任意两点之间都可以修一条新路 ⇒ 这是一张**完全图**，n(n−1)/2 = 499 500 条边。
//   已经修好的那 m 条，**权值当 0**（不用再花钱）⇒ 剩下的就是一句最小生成树。
//
// ⇒ 完全图 ＋ n = 1000 ⇒ 本章第 12 步那张表里「**朴素 Prim 占优**」的那一档：
//   O(n²) = 10⁶，而 Kruskal 要先摊开 499 500 条边再排序。实测见本页第 ⑥ 步。
//
// ⚠⚠ 两处会咬人的：
//   ① 坐标 ≤ 10⁶ ⇒ `dx * dx` 最大 10¹² —— **int 装不下**（见 p2872Int.cpp）；
//   ② 题面明写「请用 **64 位**实型变量进行计算」⇒ `double` 不是 `float`（见 p2872Float.cpp）。


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


const int N = 1005;
int x[N], y[N];
double g[N][N];


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];   // ★ long long：10¹² 装不进 int
            g[i][j] = sqrt((double)(dx * dx + dy * dy));
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 0.0;                            // ★ 已经修好的路，权值当 0
    }


    vector<char> in(n + 1, 0);
    vector<double> best(n + 1, 1e18);
    best[1] = 0;
    double sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        sum += best[u];                                     // ★ 加的是**距离**，不是距离的平方
        for (int i = 1; i <= n; i++)
            if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }


    printf("%.2f\n", sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果

2★★★ 这道题最经典的一发 WA：dx * dx 用了 int

p2872Int.cpp✗ dx * dx 在 int 里算（官方样例照样打出 4.00）
// ✗ P2872：算 dx * dx 的时候用了 int
//
// ★★★ 这是这道题最经典的一发 WA，而它是**一道三十秒的算术题**：
//   题面写着 `1 ≤ xᵢ, yᵢ ≤ 10⁶` ⇒ `dx` 最大 999 999 ⇒ `dx * dx` 最大 **≈ 10¹²**，
//   而 `int` 只到 2 147 483 647（≈ 2.1 × 10⁹）—— **差三个数量级。**
//
// ⚠ 分界线算得出来：`46340² = 2 147 395 600 < 2³¹`，`46341² = 2 147 488 281 > 2³¹`
//   ⇒ **只要有一个坐标差 ≥ 46 341，单是那一项就溢出了**
//   （[第 18 章 P1516](/sol/p1516/) 那条分界线，一字不差地又出现了一次）。
// ⇒ 而顺手把坐标压到 1000 以内的生成器，**结构上**造不出溢出。


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


const int N = 1005;
int x[N], y[N];
double g[N][N];


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int dx = x[i] - x[j], dy = y[i] - y[j];         // ✗ int
            g[i][j] = sqrt((double)(dx * dx + dy * dy));    // ✗ 乘法在 int 里就已经绕回去了
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 0.0;
    }


    vector<char> in(n + 1, 0);
    vector<double> best(n + 1, 1e18);
    best[1] = 0;
    double sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++) if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        sum += best[u];
        for (int i = 1; i <= n; i++) if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    printf("%.2f\n", sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★★ 一道三十秒的算术题，而分界线是一个能写出来的整数

题面写着 1 ≤ xᵢ, yᵢ ≤ 10⁶ ⇒ dx 最大 999 999 ⇒ dx * dx 最大 ≈ 10¹²， 而 int 只到 2 147 483 647 —— 差三个数量级。

⚠ 而「多大才会炸」精确到个位：
46340² 2 147 395 600 ＜ 2³¹−1 ✓
int 上限 2 147 483 647
46341² 2 147 488 281 ＞ 2³¹−1 ✗

⇒ 只要有一个坐标差 ≥ 46 341，单是那一项就已经绕回去了。 ★ 这条分界线和第 18 章 P1516 那次一字不差（那道题是 46340² < 2³¹ ≤ 46341²）—— ⇒ 它不是这道题的性质，是 int 的性质，值得背下来。

★★ 而顺手写的生成器把坐标压到 1000，这个 bug 就是精确的 0
300 轮 ★ 档 0 坐标 ≤ 1000 ★★ 档 1 坐标照题面顶格
真的有一对点使 dx² + dy² 撑破 int ★ 0 300
⇒ 「用 int」被抓 ★ 0 ★ 300

★ 触发条件 ≡ 抓获数，四个档一个不差。 ⇒ 又一次「顶格是顶到题面的边上」：坐标压小不是「数据弱」，是结构上碰不到那条线。

3⚠ 题面自己提醒的那半句：请用 64 位实型

p2872Float.cpp✗ 用 float 存和累加（官方样例照样打出 4.00）
// ✗ P2872：用 float 存距离和累加
//
// 题面里那半句「**为了避免误差，请用 64 位实型变量进行计算**」，就是冲这一版来的。
//
// ★ 一道三十秒的算术题：答案上界 ≈ `999 × √2 × 10⁶` ≈ **1.41 × 10⁹**，
//   而 `float` 只有 **24 位尾数**（约 7 位十进制有效数字）
//   ⇒ 在 10⁹ 这个量级上，它连**个位**都表示不了，更别说题目要的**两位小数**。
// ⚠ 而坐标压小的生成器**几乎**看不见它 —— 实测 300 轮只抓到 **2** 次
//   （答案才三位数时 float 绰绰有余）；坐标照题面顶格才是 **256 / 300**。
//   ⇒ 注意这个「几乎」：它不是[精确的 0](/sol/p3366/)，是一个很小的正数 ——
//     **两种情况要用不同的办法救**（前者只能改结构，后者加轮数也行）。


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


const int N = 1005;
int x[N], y[N];
float g[N][N];


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            g[i][j] = (float)sqrt((double)(dx * dx + dy * dy));   // ✗ 存进 float 就掉精度了
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 0.0f;
    }


    vector<char> in(n + 1, 0);
    vector<float> best(n + 1, 1e30f);
    best[1] = 0;
    float sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++) if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        sum += best[u];                                        // ✗ 累加也在 float 里
        for (int i = 1; i <= n; i++) if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    printf("%.2f\n", (double)sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★ 又是一道三十秒的算术题 —— 而这次题面把答案写在输出格式里了

「为了避免误差，请用 64 位实型变量进行计算。」
答案上界 ≈ 999 × √2 × 10⁶ 1 412 799 349（≈ 1.41 × 10⁹）
float 的十进制有效数字 ★ 约 7 位
double 约 16 位

⇒ 在 10⁹ 这个量级上，float 连个位都表示不了，而题目要的是两位小数。

300 轮 档 0 坐标 ≤ 1000 档 1 坐标顶格 档 2 已有路多 档 3 顶格 ＋ n = 6
float 版和 double 版打出的字符串不同 2 256 ★ 0 275
⇒ 「用 float」被抓 ★ 2 ★ 256 ★ 0 ★ 275

★ 又一个四档一个不差。 ⚠⚠ 而注意档 0 那个 2 —— 它不是精确的 0，是一个很小的正数。 ⇒ 「精确的 0 和掉了一百倍要用不同的办法救」： 前者只能改结构，后者加轮数也行。写「坐标压小就看不见它」是不准确的， 准确的说法是「几乎看不见（2 / 300）」。

4★★★ 同一个「用平方代替距离」的念头，一半对一半错

sqrt 是这份代码里最贵的一步，而 Prim 每一轮只是在比大小 —— 于是很自然会想：能不能干脆存距离的平方，省掉那 10⁶ 次开方？

p2872Sq.cpp★ 比较用平方 —— 它是对的（1200 轮逐字节相同）
// ⚠ P2872：**比较**用距离的平方（不开方），只在累加的时候才 sqrt —— 而它是**对的**
//
// ★★★ 想法很自然：`sqrt` 慢，而 Prim 每一步只是在**比大小** ——
//   而 `a < b ⟺ a² < b²`（两边都非负）⇒ **比较用平方完全等价**。
// ⇒ 实测和正解 300 组逐字节相同（本页第 ⑤ 步）。
//
// ⚠⚠ 但**只有比较能这么干**：`√a + √b ≠ √(a + b)` ——
//   把累加也换成平方就当场错（见 p2872SumSq.cpp，300 / 300）。
//   ⇒ **同一个「用平方代替距离」的念头，一半是对的一半是错的**，
//     而分界线正好落在「比较」和「求和」之间。


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


const int N = 1005;
int x[N], y[N];
long long g[N][N];                                          // ★ 存的是距离的**平方**


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            g[i][j] = dx * dx + dy * dy;
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 0;
    }


    vector<char> in(n + 1, 0);
    vector<long long> best(n + 1, LLONG_MAX);
    best[1] = 0;
    double sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!in[i] && (u < 0 || best[i] < best[u])) u = i;   // ★ 比较：平方就够
        in[u] = 1;
        sum += sqrt((double)best[u]);                            // ★ 求和：必须先开方
        for (int i = 1; i <= n; i++)
            if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    printf("%.2f\n", sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
p2872SumSq.cpp✗ 连求和也用平方（样例打出 2.83，当场挡住）
// ✗ P2872：连**求和**也用了距离的平方，最后才开一次方
//
// ★ 它是上一份（p2872Sq.cpp，**对的**）只挪了一个括号的产物：
//     ✓ `sum += sqrt(best[u])`     ← 每条边各自开方，再相加
//     ✗ `sum += best[u]` 最后 sqrt ← 先把平方加起来，再开一次方
//   而 `√a + √b ≠ √(a + b)`（除非有一边是 0）⇒ **每组都错**。


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


const int N = 1005;
int x[N], y[N];
long long g[N][N];


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            g[i][j] = dx * dx + dy * dy;
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 0;
    }


    vector<char> in(n + 1, 0);
    vector<long long> best(n + 1, LLONG_MAX);
    best[1] = 0;
    long long sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++) if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        sum += best[u];                                     // ✗ 把平方加起来了
        for (int i = 1; i <= n; i++) if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    printf("%.2f\n", sqrt((double)sum));                    // ✗ 最后才开一次方
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★★ 分界线正好落在「比较」和「求和」之间
成不成立 为什么
比较用平方 ★ 成立 a < b ⟺ a² < b²（两边非负）
求和用平方 ✗ 不成立 √a + √b ≠ √(a + b)

⇒ 两份代码只差一个括号的位置：

✓  sum += sqrt(best[u]);              // 每条边各自开方，再相加
✗  sum += best[u];  ... sqrt(sum)     // 先把平方加起来，再开一次方
300 轮 档 0 档 1 ★ 档 2 已有路多 档 3
最小生成树里非零的边 ≥ 2 条 286 286 ★ 0 300
⇒ 「求和也用平方」被抓 ★ 286 ★ 286 ★ 0 ★ 300

★★ 又一个四档一个不差，而且档 2 那个 0 是能证的： 非零边只有 0 条或 1 条时，√(Σw²) 恰好就等于 Σw —— 它蒙对了。 ⚠ 而这一档里有 247 / 300 组答案干脆就是 0.00（已有的路把图连满了）—— ⇒ 那些轮两版一起打出 0.00，又一次「一致有两种：都算对了，和都没算」。

5⚠ 已有的那 m 条路，忘了把它们设成 0

p2872Keep.cpp✗ 读了 m 条边却一个字没用（样例打出 6.24，挡住了）
// ✗ P2872：已经修好的那 m 条路，按实际距离算了钱
//
// 题面问的是「**添加的**边的总长度的最小值」——
// 已经存在的路是白送的，它们唯一的作用是**把两头的点先连起来**。
// ★ 顺手把 m 条已有边当成普通边一起丢进图里，就等于替它们又付了一次钱。
// ⚠ 而它只在「已有边真的会被选进最小生成树」时才现形 —— 见本页第 ④ 步那两层。


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


const int N = 1005;
int x[N], y[N];
double g[N][N];


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            g[i][j] = sqrt((double)(dx * dx + dy * dy));
        }


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;                                      // ✗ 读了，但一个字都没用上
    }


    vector<char> in(n + 1, 0);
    vector<double> best(n + 1, 1e18);
    best[1] = 0;
    double sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++) if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        sum += best[u];
        for (int i = 1; i <= n; i++) if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    printf("%.2f\n", sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
300 轮 档 0 档 1 ★ 档 2 已有路多且专挑长边 档 3
已有的路真的被选进树 181 181 ★ 300 193
⇒ 「没设成 0」被抓 ★ 181 ★ 181 ★ 300 ★ 193

★ 第四个「四档一个不差」。⇒ 这一页四个错法的触发条件，全都精确地等于它们的抓获数。

6★★ 兑现 [P1546] 那句话 —— 这道题才是 Prim 和 Kruskal 真的分开的地方

p2872Kru.cpp★ Kruskal 版 —— 也能 AC，但要先摊开 499 500 条边
// ★ P2872 的另一条路：Kruskal —— 它也能 AC，但要先摊开 499 500 条边
//
// ⚠ 这道题正是[本章第 12 步](/ch/34-mst/)那张表真正分胜负的地方：
//   [P1546](/sol/p1546/) 的 n 只有 100（4950 条边，选谁都是 5 毫秒），
//   这道题 n = 1000 ⇒ **499 500 条边**，摊开 ＋ 排序的钱就看得见了。实测见本页第 ⑥ 步。


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


const int N = 1005;
int x[N], y[N], fa[N];
int find(int a) { return fa[a] == a ? a : fa[a] = find(fa[a]); }


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


    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];


    vector<vector<char>> had(n + 1, vector<char>(n + 1, 0));
    vector<pair<int, int>> pre(m);
    for (auto& p : pre) { cin >> p.first >> p.second; had[p.first][p.second] = had[p.second][p.first] = 1; }


    vector<tuple<double, int, int>> e;
    e.reserve((size_t)n * (n - 1) / 2);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            double w = had[i][j] ? 0.0 : sqrt((double)(dx * dx + dy * dy));
            e.push_back({w, i, j});
        }


    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) fa[i] = i;


    double sum = 0;
    int cnt = 0;
    for (auto& [w, a, b] : e) {
        int p = find(a), q = find(b);
        if (p == q) continue;
        fa[p] = q;
        sum += w;
        if (++cnt == n - 1) break;
    }
    printf("%.2f\n", sum);
    return 0;
}
点一下即可编辑
输入（stdin）
输出
点「运行 ▶」看结果
★★ 同一句「稠密图用朴素 Prim」，两道题上一句白说、一句值 4.3 倍
A 机 · WSL2 · 8 核 / 7 G · 2026-08-31 · 独占 · 5 次取最小 P1546（n = 100） ★ 这道题（n = 1000）
完全图边数 4 950 ★ 499 500
朴素 Prim 5 毫秒 ★ 9 毫秒
Kruskal 5 毫秒 39 毫秒 ⇒ ★ 4.3 倍
结论 ⚠ 选型不值钱 ★ 选型值 4.3 倍

⇒ ★★ 「稠密图该用朴素 Prim」这句话的主语是 n，而 n 要够大它才值钱。 两道题连起来看，这句话的价格曲线就有两个点了。

★ 顺带把内存那笔账也做了（题面给 125 MB，两条路都放得下）：
Kruskal 的边数组（499 500 × 16 字节） 7 MB
Prim 的矩阵（1001 × 1001 × 8） 7 MB

⚠ 而「比较用平方」那一版和正解跑得一样快（9 毫秒）—— 省掉的那 10⁶ 次 sqrt 在这个规模上一分钱都不值， ⇒ 选它的理由只能是「不掉精度」，不是「更快」。

7★★★ 实数输出的题，对拍能不能逐字节比 —— 这个要量

★★★ [P2240](/sol/p2240/) 那次量出 0.93% 不同，这道题量出 0 组不同

P2240 那一页留过一句狠话：实数输出的题，对拍不能逐字节比 —— 那道题随机 20 万组里有 1861 组（0.93%），「精确值四舍五入」和 printf("%.2f") 打出的串不同。

这道题的三种正确写法（朴素 Prim ／ Kruskal ／ 比较用平方）加法顺序都不一样， 浮点加法又不满足结合律 ⇒ 完全有理由担心最后两位小数会飘。所以量了一遍：
四个档 300 轮 × 三种正确写法 ＋ 参照物，逐字节比 ★ 0 组不同
顶格 n = 1000 另跑 10 组，Prim vs Kruskal ★ 0 组不同

⇒ 这道题逐字节比是安全的 —— 而这句话是量出来的，不是推出来的。 ★★ 两页凑成一对：「实数输出要不要带容差」不是一个能背的规矩，是一道每题都要重问的题。 ⚠ 而两边的差别也说得清：P2240 的答案是个有理数、正好会落在 0.125 这种「二分正中间」上； 这道题的每一项都是 sqrt 出来的无理数，落在两位小数的正中间是零概率事件。

8★ 对拍这一页

p2872Brute.cpp参照物：枚举所有边子集（1200 轮不一致 0 轮）
300 轮（n 随机 4~6） 档 0 坐标 ≤ 1000 ★★ 档 1 坐标顶格 ★ 档 2 已有路多 ★ 档 3 顶格 ＋ n = 6
朴素 Prim（正解） ★ 0 ★ 0 ★ 0 ★ 0
Kruskal ★ 0 ★ 0 ★ 0 ★ 0
比较用平方 ★ 0 ★ 0 ★ 0 ★ 0
dx * dx 用 int ★ 0 ★ 300 ★ 0 ★ 300
用 float 2 256 ★ 0 275
求和也用平方 286 286 ★ 0 300
已有边没设 0 181 181 ★ 300 193
★★★ 这一页最值钱的一条：四个错法，四张表，四个「一个不差」
错法 触发条件 四档触发 四档被抓
dx * dx 用 int 有一对点 dx² + dy² > 2³¹−1 0 / 300 / 0 / 300 ★ 同上
用 float float 和 double 打出的串不同 2 / 256 / 0 / 275 ★ 同上
求和也用平方 树里非零边 ≥ 2 条 286 / 286 / 0 / 300 ★ 同上
已有边没设 0 已有的路真被选进树 181 / 181 / 300 / 193 ★ 同上

⇒ 四个都是能证的等价（两版只在那一件事上分家），所以「一个不差」不是巧合。 ⚠ 而别把它当定律 —— 同一页上隔壁 P1547 的重边就是 300 触发只抓 129， P1803 差 60 倍、B3637 差 150 倍。 ★★ 能不能写成「≡」，取决于你第一层写得够不够细，不取决于这条规律。

★ 官方样例这一轮挡住了四个里的两个
错法 抓获率（最狠的那一档） 官方样例挡住了吗
求和也用平方 300 / 300 ★ 挡住了（打出 2.83）
已有边没设 0 300 / 300 ★ 挡住了（打出 6.24）
dx * dx 用 int 300 / 300 ⚠ 放过了 —— 样例坐标只到 4，离 46 341 差了四个数量级
用 float 275 / 300 ⚠ 放过了 —— 样例答案才 4.00，float 绰绰有余

⇒ 四个全是「在它自己那一档上 300 / 300」的类型，而样例只挡住两个 —— ★★ 又一次：样例挡不挡得住，主语是「那组数据的结构」，不是「这个 bug 明不明显」 （P1266 那条）。

9度量程序和生成器

p2872Count.cpp度量程序（本页所有数字都出自它）
p2872Gen.cpp（五个档位）数据生成器

10一页纸
★★ 关键的一步 全在建图：完全图 499 500 条边 ＋ 已有的路权值当 0 ⇒ 剩下就是一句 MST
★★★ 最经典的一发 WA dx * dx 用 int —— 分界线 46 341，和 P1516 一字不差
⚠ 生成器 坐标压到 1000 ⇒ 那个 bug 是精确的 0；顶格才 300 / 300
★ 题面写着的 「请用 64 位实型」—— 答案量级 1.41 × 10⁹，float 只有 7 位有效数字
★★★ 一半对一半错 比较用平方成立（1200 轮逐字节相同）、求和用平方不成立
★★ 选型 这道题 Prim 9 ms / Kruskal 39 ms ⇒ 4.3 倍（P1546 上同一句话一分不值）
★★★ 实数逐字节比 这道题安全（0 组不同），而 P2240 是 0.93% ⇒ 每题都要重问
★★★ 四个一个不差 四个错法的触发条件全部 ≡ 抓获数，四档全对 —— ⚠ 但这取决于第一层写得够不够细