题解：洛谷 P1547 [USACO05MAR] Out of Hay S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P1547 [USACO05MAR] Out of Hay S - 洛谷

【题目描述】

Bessie 计划调查 $N$（$2\le N\le 2000$）个农场的干草情况，它从 $1$ 号农场出发。农场之间总共有 $M$（$1\le M\le 10^4$）条双向道路，所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

【输入】

第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个用空格隔开的整数 $A_i,B_i,L_i$，表示 $A_i,B_i$ 之间有一条道路，长度为 $L_i$。

【输出】

一个整数，表示最小生成树中的最长边的长度。

【输入样例】

3 3
1 2 23
2 3 1000
1 3 43

【输出样例】

43

【核心思想】

1. 问题分析：给定 $N$ 个农场、$M$ 条双向道路的无向连通图，求最小生成树（MST）中的最长边长度。这是一个最小生成树 + 边权追踪问题，关键在于利用 Kruskal 算法按边权从小到大选边，自然保证最后加入的边即为 MST 中的最大边。

2. 算法选择：

   • Kruskal 算法：按边权升序排序，用并查集维护连通性，每次选择不形成环的最小边
   • 最大边追踪：在 Kruskal 过程中，每次成功加入生成树时更新 maxn = max(maxn, w)，最终 maxn 即为 MST 的最长边

3. 关键步骤：

   • 读取输入：读入 $N,M$ 和 $M$ 条边 $(A_i,B_i,L_i)$
   • 边排序：按边权 $w$ 从小到大排序
   • 并查集初始化：$p[i]=i$（$i$ 从 $1$ 到 $N$）
   • Kruskal 选边（遍历排序后的边）：
     • 查找 $a=find(A_i)$，$b=find(B_i)$
     • 若 $a\ne b$（不连通）：
       • 合并：$p[a]=b$
       • 更新最大边权：maxn = max(maxn, w)
   • 输出 maxn

4. 时间/空间复杂度：

   • 时间复杂度：$O(M\log M+M\cdot \alpha (N))$，排序 $O(M\log M)$，并查集操作近似 $O(1)$
   • 空间复杂度：$O(N+M)$，并查集 + 边数组

5. Kruskal 的核心思想：

   • 贪心选边：按边权从小到大依次选择，若该边连接两个不同连通块则加入 MST。由于边权递增，最后加入的边必然是当前可选的最大边，即为 MST 的最长边
   • 并查集维护连通性：路径压缩 + 按秩合并保证近乎常数时间的连通性判断
   • MST 性质：Kruskal 的正确性基于"割性质"——全局最小边必在某棵 MST 中，按序选边保证不遗漏更优解
   • 适用于"无向图最小生成树 + 追踪特定边权"类问题，核心是按权排序后用并查集贪心选边

【算法标签】

#普及 #生成树

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, M = 10005 * 2;
int n, m, ans, p[N], maxn = -1;  // n: 节点数, m: 边数, maxn: 最大边权
struct Edge  // 存储边
{
    int a, b, 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];
}

void kruskal()  // Kruskal算法
{
    sort(edges + 1, edges + m + 1);  // 边按权值排序
    for (int i = 1; i <= n; i++)  // 初始化并查集
    {
        p[i] = i;
    }
    int res = 0;  // 总权值
    for (int i = 1; i <= m; i++)  // 遍历所有边
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if (a != b)  // 不连通，加入生成树
        {
            p[a] = b;  // 合并
            res += w;  // 累加权值
            maxn = max(maxn, w);  // 更新最大边权
        }
    }
}
int main()
{
    cin >> n >> m;  // 输入节点数和边数
    for (int i = 1; i <= m; i++)  // 输入边
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    kruskal();  // 计算最小生成树
    cout << maxn << endl;  // 输出最大边权
    return 0;
}

【运行结果】

3 3
1 2 23
2 3 1000
1 3 43
43

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/guolianggsta/article/details/167283429