首页 > 试题广场 >

寻宝

[编程题]寻宝
  • 热度指数：3201 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
亮亮解出了卷轴隐藏的秘密，来到了一片沼泽地。这里有很多空地，而面试直通卡可能埋在任意一块空地中，好在亮亮发现了一堆木材，他可以将木材铺在两个空地之间的沼泽地上。因为亮亮不知道面试直通卡具体在哪一块空地中，所以必须要保证任意一块空地对于亮亮来说是可以抵达的。 “怎么还有鳄鱼！没办法，看来有些空地不能直接到达了。” 亮亮虽然没有洁癖，但是沼泽地实在太臭了，所以亮亮不会循环利用木材。而且木材不能拼接在一起使用，所以亮亮必须要知道在耗费木材最少的情况下，最长的那根木材至少需要多长。

输入描述:
第一行包含两个整数N(1≤N≤10000),M(1≤M≤1000000)。N表示公有N块空地。
接下来M行，每行包含三个整数P(1≤P≤N),Q(1≤Q≤N),K代表P,Q两个间没有鳄鱼，需要耗费K的木材。


输出描述:
一个整数，即耗费木材最少的情况下，最长的那根木材长度。
示例1

输入

4 3
1 2 1
2 3 1
3 4 2

输出

2
算法知识视频讲解
开通博客
头像 笔寞
发表于 2021-08-05 19:49:33
/** 简单思路就是：直接用kruskal算法来求最小生成树，最长那一条边就是答案--- kruskal算法天生容易求最长边 1. 建立一个类存储顶点a ,顶点b, 权重w，将所有边放直接根据边来排序. 2. 搞个并查集。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 重生之我要当分子
发表于 2025-01-02 21:36:58
解题思路 这是一个最小生成树问题，需要找到连接所有空地的最小生成树，并且要求最长的边最小。这种问题可以使用Kruskal算法的变体来解决。 关键点： 使用Kruskal算法构建最小生成树 按照边的长度排序 使用并查集维护连通性 找到满足条件的最小最大边 算法步骤： 对所有边按长度排序 使用二分 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 只想至圣斩
发表于 2024-10-21 21:47:24
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Edge{ int u,v,w; bool operator<(c 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 图 测试工程师 PHP工程师 2016 楚楚街 贪心 2018 Java工程师 牛客
来自：楚楚街2016非北京地...
难度：
31条回答 12732浏览

热门推荐

通过挑战的用户

查看代码

相关试题

寻宝

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号