#UVA1395

UVA1395 Slim Span(kruskal)

题目:SlimSpanUVA1395题意:给出一副无向有权图,求生成树中最小的苗条度(最大权值减最小权值),如果不能生成树,就输出-1;思路:将所有的边按权值有小到大排序,然后枚举每一条边,以这条边开始利用Kruskal算法生成树,生成过程中求出权值的最大值,这个最大值减去当前枚举的边的权值就是苗条度,再动态维护一下最...
代码星球 ·2020-07-18