定义一颗树的苗条度为这棵树的最大边权与最小边权的差值。
现在有一个 n个点 m 条边的无向联通图,求苗条度最小的生成树的苗条度是多少。
如图所示的数据中:最优的选取方案选取的生成树的三条边分别为 (1-4,4-2,1-3) ,所以答案为 100-80=20 。
第 1行:两个正整数 n,m,n 表示图中点的个数, m表示图中边的个数。 (2<=n<=100,0<=m<=n*(n-1)/2)
第 2 行-第 m+1 行:每行 3 个正整数, u,v,w ,表示 u 和 v 之间有一条权值为 w 的边。 (1<=u,v<=n,1<=w<=10000)
输出一个整数表示苗条度最小的生成树的苗条度。
4 6 1 2 10 1 3 100 1 4 90 2 3 20 2 4 80 3 4 40
20