从一道 GESP 真题出发：聊聊带约束的最小生成树与贪心选边

COCOgsta

271人浏览 · 2026-08-24 09:01:31

COCOgsta · 2026-08-24 09:01:31 发布

题源链接：洛谷 P17016 [GESP202606 八级] 线网建设

一、背景

在算法竞赛的图论专题中，有一类问题特别贴近现实——它们不是抽象的数学游戏，而是真实的工程问题披着竞赛的外衣。GESP 八级的这道线网建设题，就是一个绝佳的例子。

题目场景很接地气：A 市有 $n$ 座基站，要在它们之间修建线路，让任意两座基站都能互相连通。但修路不是想修就能修的——两座基站之间只有当距离不超过 $l$ 时才能拉线。目标是：在满足连通性的前提下，总线路长度最短。如果根本无法让所有基站连通，就输出 Impossible。

这道题的本质，是在一个带距离约束的完全图上求最小生成树（Minimum Spanning Tree，MST）。但和教科书上的标准 MST 不同，这里多了一个"距离上限"的约束，把很多边直接"砍掉了"。本文就从这道线网建设题出发，聊聊Kruskal 算法的核心思想、并查集的高效实现，以及约束预处理在图论问题中的重要性。

二、核心思想

2.1 从"修路问题"到"最小生成树"

拿到这道题，很多选手可能会先想到：把所有能修的边都修上，然后看看能不能连通？但这显然不是最优的——修多了浪费钱。我们需要的是在保证连通的前提下，总长度最小。

这正是最小生成树的定义：在一个带权无向图中，选择 $n - 1$ 条边，使得所有结点连通，且总权重最小。生成树之所以是"树"，是因为 $n$ 个结点最少需要 $n - 1$ 条边才能连通，再多就会形成环，而环上的任意一条边都可以去掉而不影响连通性。

但本题还有一个额外的约束：只有当两基站距离 $\leq l$ 时，边才存在。这就像在修公路时，有些地方地形太险（距离太远），根本没法修隧道。所以我们不能直接用标准的 MST 算法，而需要先筛选有效边。

这个问题的特征：

连通性 + 最小代价：既要保证连通，又要总长度最短
约束预处理：距离上限 $l$ 把完全图变成了稀疏图，需要先过滤
可行性判定：不是所有情况下都能连通，需要判断并输出 Impossible

2.2 Kruskal 的贪心直觉：每次选最短的"桥"

Kruskal 算法的核心思想非常直观：在所有能连接两个不同连通块的边中，永远选最短的那条。

我们可以把基站想象成散落在地图上的村庄，算法的过程就像这样：

一开始，每个村庄都是独立的"岛屿"
你手边有一堆候选桥梁（有效边），按长度排好序
每次拿出最短的一座桥，如果它连接的是两个不同的岛屿，就修上它，把两个岛合并
如果它连接的是同一个岛内的两个点，就跳过（修它会形成环，浪费钱）
重复直到所有村庄都在一个大岛上，或者候选桥用完了

这个策略为什么是对的？因为割性质告诉我们：对于图的任意一个割（把结点分成两组），跨越这个割的最短边一定属于某棵最小生成树。Kruskal 每次选的边，本质上就是在某个割上选最短边。

Kruskal 的特征：

全局贪心：按边权全局排序，而非从某个起点局部扩展
并查集维护：高效判断两个结点是否在同一个连通块
天然处理不连通：如果候选边用完还没连完所有点，直接判定不可行

2.3 并查集：连通块的"身份证系统"

Kruskal 算法需要一个高效的数据结构来回答一个问题："这两个结点已经在同一个连通块里了吗？"如果回答是，这条边就不能选（会形成环）；如果回答否，就选这条边，并把两个连通块合并。

并查集（Disjoint Set Union，DSU）就是干这个的。它给每个连通块分配一个"代表"（根结点），每个结点指向自己的代表。查询时沿着指针找到根，合并时把一个根的指针指向另一个根。

并查集有两个经典优化：

路径压缩：查询时把沿途所有结点的指针直接指向根，下次查询就快了
按秩合并：合并时把小的树挂到大的树下，保持树高较低

这两个优化叠加后，单次操作的均摊复杂度接近 $O (a l p ha (n))$ ，其中 $a l p ha$ 是阿克曼函数的反函数，增长极其缓慢，实际可以视为常数。

我们可以把并查集想象成一个家族谱系查询系统：

每个结点是一个人
同一连通块的人是同一个"家族"
查询就是问"这两个人是不是同一家族的？"
合并就是两个家族联姻，变成一个大家族
路径压缩就是"直接认族长做祖宗，省得一层层问"

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"智能修路机"：

勘测地形：计算所有基站对的距离，只保留距离 $\leq l$ 的候选路线
按成本排序：把所有候选路线按长度从小到大排好队
贪心修路：从最短的开始，如果这条路连接的是两个不同的"施工区域"，就修上；否则跳过
区域合并：每修一条路，就把两个施工区域合并成一个
完工检查：如果修了 $n - 1$ 条路，所有基站连通了；否则输出 Impossible

整个过程就像拼图游戏：先把能拼的碎片（有效边）找出来，按大小排好，然后一块一块拼，确保每次拼的都是连接两个独立部分的最小碎片。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 带约束最小生成树(基站[1..n], 距离上限 l):
    edges = []
    for i = 1 to n:
        for j = i+1 to n:
            d = 欧几里得距离(基站[i], 基站[j])
            if d <= l:
                edges.append(边(i, j, d))

    if edges 为空:
        return "Impossible"

    sort(edges by 长度升序)
    初始化并查集

    res = 0, cnt = 0
    for each edge (a, b, w) in edges:
        if find(a) != find(b):
            union(a, b)
            res += w
            cnt++

    if cnt < n - 1:
        return "Impossible"
    else:
        return res

实战代码（通用模板）：

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

const int N = 505;
const int M = N * N;
const double INF = 1e18;

int n;
double l;
int x[N], y[N];
int p[N];
int cur;

struct Edge
{
    int a, b;
    double w;
    bool operator < (const Edge &E) const
    {
        return w < E.w;
    }
} edges[M];

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

double kruskal()
{
    sort(edges + 1, edges + cur + 1);

    for (int i = 1; i <= n; i++)
        p[i] = i;

    double res = 0;
    int cnt = 0;

    for (int i = 1; i <= cur; i++)
    {
        int a = edges[i].a, b = edges[i].b;
        double w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    if (cnt < n - 1)
        return INF;
    return res;
}

int main()
{
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
            if (d <= l)
                edges[++cur] = {i, j, d};
        }

    double ans = kruskal();
    if (ans != INF)
        printf("%.2lf\n", ans);
    else
        printf("Impossible\n");

    return 0;
}

3.3 例题实现 —— 本题完整代码

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

#define int long long
const int N = 505, M = N * N, INF = 1e18;  // N: 最大点数; M: 最大边数; INF: 无穷大

int x[N], y[N];                    // x[i], y[i]: 第 i 座基站的坐标
double l;                          // l: 线路长度上限
double ans;                        // ans: 最小生成树的总长度
int n, m;                          // n: 基站数量; m: 边数（未使用）
int cur;                           // cur: 当前有效边数
int p[N];                          // p[i]: 并查集中 i 的父节点
double w[N][N];                    // w[i][j]: 基站 i 和 j 之间的欧几里得距离

struct Edge                        // 边结构体
{
    int a, b;                      // a, b: 边的两个端点
    double w;                      // w: 边的长度

    bool operator < (const Edge &E)const  // 重载小于号，用于按边长排序
    {
        return w < E.w;
    }
} edges[M];                        // edges: 存储所有有效边

int find(int x)                    // 并查集查找操作，带路径压缩
{
    if (p[x] != x)
        p[x] = find(p[x]);

    return p[x];
}

double kruskal()                   // Kruskal 算法求最小生成树
{
    sort(edges + 1, edges + cur + 1);  // 按边长从小到大排序

    for (int i = 1; i <= n; i++)  // 初始化并查集
        p[i] = i;

    double res = 0;                // res: 当前生成树的总长度
    int cnt = 0;                   // cnt: 已选入生成树的边数

    for (int i = 1; i <= cur; i++)  // 遍历所有有效边
    {
        int a = edges[i].a, b = edges[i].b;  // 边的两个端点
        double w = edges[i].w;     // 边的长度

        a = find(a), b = find(b);  // 查找两个端点所在连通块的根

        if (a != b)                // 如果不在同一连通块，加入该边
        {
            p[a] = b;              // 合并两个连通块
            res += w;              // 累加边长到总长度
            cnt++;                 // 边数加一
        }
    }

    if (cnt < n - 1)               // 如果边数不足 n-1，图不连通
        return INF;

    return res;
}

signed main()
{
    cin >> n >> l;                 // 读入基站数量和线路长度上限

    for (int i = 1; i <= n; i++)  // 读入每座基站的坐标
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)  // 初始化并查集
        p[i] = i;

    for (int i = 1; i <= n; i++)  // 枚举所有基站对，计算距离并筛选有效边
        for (int j = i + 1; j <= n; j++)
        {
            // 计算欧几里得距离
            w[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

            if (w[i][j] > l)       // 如果距离超过上限，设为无穷大（不可用）
                w[i][j] = 1e18;
            else
                edges[++cur] = {i, j, w[i][j]};  // 加入有效边集合
        }

    double ans = kruskal();        // 执行 Kruskal 算法

    if (ans != INF)                // 如果存在最小生成树
        printf("%.2lf\n", ans);    // 输出最小总长度，保留两位小数
    else
        printf("Impossible\n");    // 图不连通，输出 Impossible

    return 0;
}

3.4 对比实现 —— Kruskal vs Prim

最小生成树有两大经典算法，各有优劣：

算法	核心思想	时间复杂度	适用场景
Kruskal（本题做法）	全局排序 + 并查集	$\log m)$	边数较少（稀疏图），实现简单
Prim	从一个点出发，逐步扩展	$O(n^2)$ 或 $\log n)$	边数较多（稠密图），尤其是完全图

对于本题， $\leq 500$ ，有效边数 $\leq C_n^2 \approx 1.25 \times 10^5$ ，Kruskal 的 $\log m)$ 完全够用。但如果 $n$ 很大（如 $10^5$ ）且图是稠密的，Prim 的堆优化版本 $\log n)$ 可能更优。

另一个值得注意的替代方案是Boruvka 算法：并行地给每个连通块找最短出边，时间复杂度 $\log n)$ ，适合分布式实现，但竞赛中较少使用。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
有向图版本	线路有方向，求最小树形图	无向边变有向弧	用朱刘算法（Edmonds’ Algorithm）求最小树形图
指定根结点	必须以某基站为根	增加根约束	Kruskal 不受影响，Prim 从指定根开始
次小生成树	求第二小的生成树	目标函数变化	先求 MST，再枚举替换边
最小瓶颈生成树	使最大边权最小	目标函数变化	Kruskal 选到 $n - 1$ 条边时的最大边权即为答案
带权点 + 带权边	基站建设也有成本	增加点权	转化为边权（拆点），再求 MST
动态加基站	基站逐个加入，维护 MST	图动态变化	动态 MST 算法，或离线处理
多约束条件	除距离外还有带宽、成本等约束	多维约束	转化为多目标优化，或约束转化为边权

3.6 什么时候不能用？——边界条件和反例

Kruskal 算法虽然万能，但也有需要注意的边界：

图不连通：如果有效边不足以连接所有结点，Kruskal 会提前结束，此时需要特判输出 Impossible。本题中通过 cnt < n - 1 来判定。
重边处理：如果两基站之间有多条有效边（本题不会，因为基站对唯一），保留最短的那条即可，其他重边在 Kruskal 中自然会被跳过。
自环：题目保证无自环，但如果有，直接忽略（一个结点不可能和自己形成连通块）。
浮点精度：本题涉及欧几里得距离（浮点数），比较时需要注意精度问题。但本题的距离上限 $l$ 是整数，距离比较用 <= 即可，排序和累加用 double 足够。
并查集初始化：每次运行 Kruskal 前必须重新初始化并查集，否则上一次查询的连通状态会干扰当前结果。

四、底层逻辑

4.1 为什么 Kruskal 的贪心策略是对的？

这是最小生成树理论中最经典的结论之一，基于割性质（Cut Property）：

对于图的任意一个割（将结点集 $V$ 划分为两个非空子集 $S$ 和 $V - S$ ），如果一条边 $(u, v)$ 是跨越这个割的所有边中权重最小的，那么这条边一定属于某棵最小生成树。

Kruskal 每次选全局最短边 $(u, v)$ ，考虑将图按并查集的连通状态划分为两个集合：包含 $u$ 的连通块和包含 $v$ 的连通块。 $(u, v)$ 是跨越这个割的边（因为 $u$ 和 $v$ 不在同一连通块），而且它是当前所有跨越割的边中最短的（因为边已按全局排序）。根据割性质， $(u, v)$ 属于某棵 MST，选它不会错。

这个证明的优雅之处在于：它不需要知道 MST 长什么样，只需要证明每一步的局部选择都不会破坏全局最优。

4.2 与经典问题的对比

这道题和经典的 MST 问题家族有密切联系：

问题	约束条件	算法	时间复杂度
标准 MST	无额外约束	Kruskal / Prim	$\log m)$ / $O(n^2)$
本题：带距离约束 MST	距离 > $l$ 的边不可用	Kruskal + 预处理筛选	$O(n^2 \log n)$
最小斯坦纳树	只需连接指定子集	状态压缩 DP + MST	指数级
度受限 MST	每个结点度数有上限	启发式 / 近似算法	NP-hard（一般情况）
最小生成森林	不强制连通所有点	Kruskal 提前终止	$\log m)$

可以看到，约束预处理是连接标准 MST 和本题的关键桥梁。通过先筛选有效边，我们把一个"带约束的 MST"问题，转化为了标准 MST 问题。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

欧几里得距离： $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ ，涉及浮点数运算。在筛选有效边时，用 d <= l 判断，不需要开方后比较——实际上可以直接比较平方距离 $d^2 \leq l^2$ ，避免浮点误差。但本题数据范围小，开方也无妨。
保留两位小数：输出格式要求精确到两位小数，使用 printf("%.2lf\n", ans) 即可。注意浮点数的四舍五入问题。
$n = 1$ 的情况：只有一个基站时，不需要修任何路，总长度为 $0$ 。但 Kruskal 中 cnt < n - 1 即 cnt < 0，显然满足，会错误输出 Impossible。需要特判 $n = 1$ 时直接输出 0.00。
坐标范围：题目未明确给出坐标范围，但使用 int 存储坐标足够（一般竞赛坐标范围在 $±109 \pm 10^9$ 内）。

五、决策表

面对"连接所有点，最小化总代价"类问题，如何根据约束和规模快速选型？

场景特征	推荐方案	时间复杂度	备注
无约束，边数较少	Kruskal + 并查集	$\log m)$	最通用，实现简单
无约束，稠密图（完全图）	Prim（数组实现）	$O(n^2)$	不需要建边表，空间省
有距离/带宽等约束	先筛选有效边 + Kruskal	$O(n^2 \log n)$	本题场景
动态加边/删边	动态 MST 算法	$O(\log n)$ 每次	较复杂，竞赛中较少
只需连接指定子集	最小斯坦纳树	指数级	状态压缩， $\leq 10$ 时可用
有向图	朱刘算法（最小树形图）	$O (nm)$ 或 $\log n)$	指定根结点

一句话总结：稀疏图用 Kruskal，稠密图用 Prim；有约束先过滤，不连通要特判。

六、工程视角

最小生成树和并查集的思想在实际工程中有着广泛的应用：

网络拓扑设计（本题直接应用）：电信网络、光纤骨干网、电力传输网等，都需要在满足连通性的前提下最小化建设成本。Kruskal 算法的贪心策略正是这类工程问题的数学基础。实际工程中还会加入更多约束（如节点容量、链路带宽、可靠性要求），形成更复杂的优化模型。
图像分割（计算机视觉）：在图像处理中，将像素视为图的结点，像素间的相似度作为边权，MST 可以用来做图像分割。通过控制"距离上限"（类似本题的 $l$ ），可以控制分割的粒度。并查集则用于高效维护像素区域的合并。
聚类分析（机器学习）：在单链接聚类（Single-linkage Clustering）中，数据点之间的距离构成完全图，MST 的切割可以用来生成层次聚类。每次去掉 MST 中最长的一条边，就把数据分成两个簇，重复这个过程可以得到聚类树。
电路板布线（EDA）：在集成电路设计中，需要在芯片上连接多个引脚，同时最小化导线总长度（减少电阻和信号延迟）。这直接对应 MST 问题。并查集则用于检测布线是否形成短路（环）。

七、小结

本文从一道 GESP 八级真题出发，探讨了带约束的最小生成树与Kruskal 贪心选边问题。

核心认知可以总结为：

当问题需要在连通性和最小代价之间做权衡时，先通过约束条件缩小候选集，再用 Kruskal 的贪心策略在候选集中选边，是工程上最可靠、竞赛中最简洁的解法。

用公式化的语言概括：

$\min_{T \subseteq E_{valid}, |T| = n-1} \sum_{(u,v) \in T} d(u, v)$

其中 $E_{valid} = \{(i, j) \mid d(i, j) \leq l\}$ 是有效边集， $T$ 是生成树。

这道题教会我们的，不仅是如何写并查集和排序，更是一种**“先约束、后优化”**的工程思维：在真实世界中，资源总是有限的（距离上限 $l$ ），先排除不可行的方案，再在可行集中寻找最优，是解决问题的标准流程。Kruskal 算法的贪心策略告诉我们，有时候"每一步都选当前最好的"，真的能得到全局最优——但前提是，这个问题的结构满足割性质。在算法竞赛中，识别出这种结构，比记住某个具体算法更重要。