ad1 广告
 
收藏文章 楼主

洛谷1111题:基于Kruskal算法与并查集的最小生成树实现

版块:闲聊杂谈   类型:普通   作者:用意要   查看:19   回复:0   获赞:0   时间:2025-06-22 10:48:02

截图未命名.jpg


一、题目解读

洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法(如Kruskal)的应用,需要高效处理边权重与节点连通性。

二、解题思路

代码采用Kruskal算法与并查集的结合,巧妙解决最小生成树问题。其核心思路为:

    1. 贪心策略:按边权重递增排序,优先选择权值最小的边;

    2. 连通性判断:利用并查集快速合并节点,避免形成环。

通过这两个关键步骤,算法能在O(ElogE)复杂度下高效求解。

三、解题步骤

1. 输入与初始化:

    读取节点数N和边数M,创建边集合edges;

    初始化并查集parent数组(每个节点初始为自身根节点)。

2. 边排序:对edges按权值t升序排序,确保后续按权重递增处理。

3. 核心循环:遍历每条边,执行合并操作:

    通过find函数获取边两端节点的真实根节点;

    若根节点不同,合并节点并更新最大边权值max_t。

4. 结果判断:若合并次数达到N-1(即形成一棵树),输出max_t;否则输出-1(图不连通)。

四、代码与注释

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 边结构(节点u、v及权值t)
struct Edge {
    int u, v, t;
    bool operator<(const Edge& other) const {
        return t < other.t; // 按权值排序比较函数
    }
};

vector<int> parent; // 并查集:记录节点的根节点

// 查找节点x的根节点(路径压缩优化)
int find(int x) {
    return parent[x] == x? x : parent[x] = find(parent[x]);
}

// 合并节点x与y,返回是否成功(避免环)
bool unite(int x, int y) {
    x = find(x); // 获取x的根
    y = find(y); // 获取y的根
    if(x == y) return false; // 同根则不合并
    parent[y] = x; // 合并y到x
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    parent.resize(N+1); // 初始化并查集数组
    
    // 初始化:每个节点为独立根节点
    for(int i=1; i<=N; i++) parent[i] = i;
    // 输入边信息
    for(int i=0; i<M; i++) 
        cin >> edges[i].u >> edges[i].v >> edges[i].t;
    
    // 按权值排序
    sort(edges.begin(), edges.end());
    
    int cnt = 0, max_t = 0; // 合并次数与最大边权
    for(auto& e : edges) {
        // 若合并成功且未形成完整树,更新信息
        if(unite(e.u, e.v)) {
            max_t = max(max_t, e.t);
            if(++cnt == N-1) break; // 树已生成,退出循环
        }
    }
    
    // 根据连通性输出结果
    cout << (cnt == N-1? max_t : -1) << endl;
    return 0;
}

五、总结

本解法通过Kruskal算法与并查集的深度融合,实现了高效的最小生成树构建。其优势在于:

1. 时间复杂度优化:排序+并查集降低处理复杂度;

2. 代码简洁性:结构清晰,逻辑易懂,适合竞赛与工程场景。

该思路为同类图论问题提供了通用解决方案,尤其在稀疏图环境中表现优异。

来源:洛谷1111题解题全解析:基于Kruskal算法与并查集的最小生成树实现

 
ad1 广告位8,870 x auto
回复列表
默认   热门   正序   倒序

回复:洛谷1111题:基于Kruskal算法与并查集的最小生成树实现

Powered by 免费外链论坛

©2015 - 2025 免费外链论坛

免费外链论坛 免费发布外链 发外链平台Sitemap

您的IP:216.73.216.77,2025-07-02 06:07:28,Processed in 0.0231 second(s).

备案信息:浙ICP备2024090696号

声明:本站内容为用户自主发布,不对其内容真实性负责,虽然本站会一一审核,但能力有限,如您发现违规内容,请及时联系管理员。

主页

欢迎您的浏览

QQ联系图标

自助查询

99%的问题都能找到答案

联系站长

工作时间:9:00~17:30

微信二维码

回到顶部

向上滚动到顶部

个人中心

去个人首页看看吧

转到底部

向下滚动到底部

头像

用户名:

粉丝数:

签名:

资料 关注 好友 消息