Slim Span
Time Limit: 5000MS |
|
Memory Limit: 65536K |
Total Submissions: 2967 |
|
Accepted: 1579 |
Description
Given an undirected weighted graph G, you should find one of spanning trees specified as follows.
The graph G is an ordered pair (V, E), where V is a set of vertices {v1,
v2, …, vn} and E is a set of undirected edges {e1,
e2, …, em}. Each edge e ∈ E has its weight
w(e).
A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with
n − 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the
n − 1 edges of T.
Figure 5: A graph
G and the weights of the edges
For example, a graph G in Figure 5(a) has four vertices {v1,
v2, v3, v4} and five undirected edges {e1,
e2, e3, e4, e5}. The weights of the edges are
w(e1) = 3, w(e2) = 5,
w(e3) = 6, w(e4) = 6, w(e5) = 7 as shown in Figure 5(b).
Figure 6: Examples of the spanning trees of
G
There are several spanning trees for G. Four of them are depicted in Figure 6(a)~(d). The spanning tree
Ta in Figure 6(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree
Ta is 4. The slimnesses of spanning trees Tb,
Tc and Td shown in Figure 6(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree Td in Figure 6(d) is one of the
slimmest spanning trees whose slimness is 1.
Your job is to write a program that computes the smallest slimness.
Input
The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.
Every input item in a dataset is a non-negative integer. Items in a line are separated by a space. n is the number of the vertices and m the number of the edges. You can assume 2 ≤
n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2. ak and
bk (k = 1, …, m) are positive integers less than or equal to
n, which represent the two vertices vak and
vbk connected by the kth edge ek.
wk is a positive integer less than or equal to 10000, which indicates the weight of
ek. You can assume that the graph G = (V,
E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).
Output
For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, −1 should be printed. An output should not contain extra characters.
Sample Input
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
1
20
0
-1
-1
1
0
1686
50
Source
分享到:
相关推荐
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
不敢说最全的,但是包含了多数poj图论题目汇总,一点一点打上去的负伤的是题目的类型,相当全面,挣点分不过分吧……
初学acmer必练题,包括图论,动态规划,和数论的基础题
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
很好很强大 的poj图论题目的分类手册啊
西北工业大学POJ试题C++答案代码+课程设计
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
POJ图论相关题目 、解析 及源代码 RT RT RT RT RT RT RT
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
北大POJ1159-Palindrome 解题报告+AC代码
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码