首页 > 试题广场 >

生成树

[编程题]生成树
  • 热度指数：416 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,给出一张由 n 个点 m 条带边权的边构成的无向连通图，你有恰好 k 次机会，选择一条边使得其边权 \sf +1 。在 k 次操作全部完成后，你要选出一个合法的生成树，使得这棵生成树中：边权最小的边最大。
\,\,\,\,\,\,\,\,\,\,输出这个边权。

\,\,\,\,\,\,\,\,\,\,对于一张图，选择其中 n-1 条边，使得所有顶点联通，这些边一定会组成一棵树，即为这张图的一棵生成树。可以证明，图中存在至少一棵生成树。

输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入三个整数 n,m,k \left( 1 \le n,m\le 10^5;\ 1 \le k \le 10^{14}\right) 代表给定图的点数、边数和你的操作次数。
\,\,\,\,\,\,\,\,\,\,此后 m 行，第 i 行输入三个整数 a_i,b_i,c_i \left( 1\le a_i,b_i \le n;\ 1 \le c_i \le 10^{14}\right) 代表图上第 i 条边连接节点 a_i 和 b_i，且边权为 c_i 。保证图联通，没有重边。


输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表全部生成树中、边权最小的边最大的那棵树，它的边权最小的边。
示例1

输入

3 2 2
1 2 1
2 3 1

输出

2

说明

\,\,\,\,\,\,\,\,\,\,由于只有两条边，只能生成一棵生成树，最优的办法是将两条边的边权各 \sf +1 。
示例2

输入

5 7 3
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

输出

7

说明

\,\,\,\,\,\,\,\,\,\,该样例如下图所示：
\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,最优的操作为对 1 到 2 这条边 \sf +3 ，生成树选择方式为：
\,\,\,\,\,\,\,\,\,\,
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

二分 淘宝闪购 图 并查集
难度：
0条回答 402浏览

热门推荐

相关试题

生成树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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