题意简述
求所有生成树中最大边权与最小边权差最小的,输出它们的差值。
输入:
输入文件包含多组测试数据,每组测试数据格式如下: 第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。
by 5u0i5n11i @ 2018-06-02 16:31:56
题意简述
求所有生成树中最大边权与最小边权差最小的,输出它们的差值。
输入:
输入文件包含多组测试数据,每组测试数据如下: 第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
```
by 5u0i5n11i @ 2018-06-02 16:34:35
@[chen_zhe](/space/show?uid=8457)
by UKE自动稽 @ 2018-06-02 17:17:06
@[kkksc03](/space/show?uid=1) @[yjjr](/space/show?uid=5088)
by andyli @ 2018-06-02 19:37:15
感谢你的翻译。
by 龟龟号打捞船 @ 2018-06-17 22:03:59
@ 商博涵123
by cstdio @ 2018-06-22 14:37:21