/ TYWZ / 题库 /

最小差值生成树 (mdt)

最小差值生成树 (mdt)

【题目描述】
给定一个无向图,求它的一棵生成树,使得生成树中的最大边权与最小边权的差最小,输出其最小差值。

【输入数据】
第一行两个整数 n(2<n<=200),m(m<=5000),分别表示点数和边数。
接下来 m 行,第 i+1 行包含三个整数 Xi(0<Xi<=n),Yi(0<Yi<=n),Di(0<Di<=10^8),表示有一条边
连接 Xi 和 Yi,距离为 Di。
保证图是连通的,两个点之间最多只有一条边。

【输出数据】
包含一行,表示最小差值生成树的最大边与最小边的差值。
【样例输入】
3 3
1 2 10
1 3 20
2 3 30
【样例输出】
10
【数据范围】:
对于30%的数据:n,m<=10;
对于60%的数据:n,m<=1000
对于100%的数据:2<n<=200,m<=5000,0<Xi<=n,0<Yi<=n,0<Di<=10^8

信息

ID
1048
难度
6
分类
(无)
标签
(无)
递交数
33
已通过
10
通过率
30%
上传者

相关