3025: 苗条的生成树[slim span,UVA1395]
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
一个无向带权图G，图G用有序对（V,G）描述，V表示图G有V的顶点{v1,v2...vn},E表示图G有E条无向边{e1,e2,...,em},每条边的权重是W(e)
图的生成树T是指一个有n个节点，n-1条边的树（没有环的子图）。生成树的跨度是指生成树的n-1条边中边的最大权重值与最小权重值的差值。
例如，如下图所示：
图G是有4个顶点{v1,v2,v3,v4}和五条无向边{e1,e2,e3,e4,e5},这五条边的权重分别是：w(e1)=3, w(e2)=5, w(e3)=6, w(e4)=6, w(e5)=7。
图G可以有很多生成树，如下图中的a b c d就是其中的4个生成树。
图a中的生成树Ta，三条边的权重分别是3，6，7，所以三条边中最大权重与最小权重的差值是4，也就是说生成树Ta的跨度是4.以此类推，生成树Tb,Tc,Td的跨度分别是3，2，1.
很明显可以看出图G的所有生成树的跨度值都大于等于1，所以生成树Td就是跨度值为1的其中的一个生成树。
你的任务是编写一个程序，计算出图G的所有生成树的最小跨度值。
图的生成树T是指一个有n个节点，n-1条边的树（没有环的子图）。生成树的跨度是指生成树的n-1条边中边的最大权重值与最小权重值的差值。
例如，如下图所示：
图G是有4个顶点{v1,v2,v3,v4}和五条无向边{e1,e2,e3,e4,e5},这五条边的权重分别是：w(e1)=3, w(e2)=5, w(e3)=6, w(e4)=6, w(e5)=7。
图G可以有很多生成树，如下图中的a b c d就是其中的4个生成树。
图a中的生成树Ta，三条边的权重分别是3，6，7，所以三条边中最大权重与最小权重的差值是4，也就是说生成树Ta的跨度是4.以此类推，生成树Tb,Tc,Td的跨度分别是3，2，1.很明显可以看出图G的所有生成树的跨度值都大于等于1，所以生成树Td就是跨度值为1的其中的一个生成树。
你的任务是编写一个程序，计算出图G的所有生成树的最小跨度值。
Input
输入包含多组测试数据。 对于每组测试数据表示一个图，格式如下： n m a1 b1 w1 . . . am bm wm 其中n表示顶点数，m表示边数，2≤n≤100，0≤m≤n*(n-1)/2 ak bk wk(k=1,2,...,m)表示顶点ak和bk间有一条边，边的权重是wk(wk≤10000)。可以认为给定的图没有自环和重边。 当输入为一行“0 0”时，表示输入结束
Output
对于每组测试数据，输出一行，输出图的所有生成树的最小跨度值。如果无解输出“-1”
Sample Input Copy
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
Sample Output Copy
1
20
0
-1
-1
1
0
1686
50