苗条的生成树 Slim Span

题意翻译

题意简述 求所有生成树中最大边权与最小边权差最小的,输出它们的差值。 输入: 输入文件包含多组测试数据,每组测试数据如下: 第1行:2个整数n m (2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2),n表示顶点数,m表示边数。接下来m行,每行3个空格分开的整数a b w(1 ≤ w ≤ 10000) , 表示顶点a与顶点b之间有一条边,权值为w。 输出: 对每组测试数据,如果图存在生成树,输出生成树的差值最小的;否则,输出-1。 样例输入: ``` 4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7 4 6 1 2 10 1 3 100 1 4 90 2 3 20 2 4 80 3 4 40 2 1 1 2 1 3 0 3 1 1 2 1 3 3 1 2 2 2 3 5 1 3 6 5 10 1 2 110 1 3 120 1 4 130 1 5 120 2 3 110 2 4 120 2 5 130 3 4 120 3 5 110 4 5 120 5 10 1 2 9384 1 3 887 1 4 2778 1 5 6916 2 3 7794 2 4 8336 2 5 5387 3 4 493 3 5 6650 4 5 1422 5 8 1 2 1 2 3 100 3 4 100 4 5 100 1 5 50 2 5 50 3 5 50 4 1 150 0 0 ``` 样例输出 ``` 1 20 0 -1 -1 1 0 1686 50 翻译提供者:Illusions

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4141 [PDF](https://uva.onlinejudge.org/external/13/p1395.pdf)

输入输出格式

输入格式


输出格式


输入输出样例

暂无测试点