本文共 895 字，大约阅读时间需要 2 分钟。

题意翻译

题意简述

求所有生成树中最大边权与最小边权差最小的，输出它们的差值。

输入：

输入文件包含多组测试数据，每组测试数据如下： 第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 51 2 31 3 51 4 62 4 63 4 74 61 2 101 3 1001 4 902 3 202 4 803 4 402 11 2 13 03 11 2 13 31 2 22 3 51 3 65 101 2 1101 3 1201 4 1301 5 1202 3 1102 4 1202 5 1303 4 1203 5 1104 5 1205 101 2 93841 3 8871 4 27781 5 69162 3 77942 4 83362 5 53873 4 4933 5 66504 5 14225 81 2 12 3 1003 4 1004 5 1001 5 502 5 503 5 504 1 1500 0

样例输出

1200-1-110168650

 思路：

首先把边按权值从小到大排序，然后枚举顶点l，以l为起点开始遍历每条边生成最小生成树，然后求差最小值。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=105;int n,m;struct edge{    int u;    int v;    int len;    int id;};edge e[maxn*maxn];int a[maxn];int compare (edge a,edge b){    return a.len
      
     
    
   

转载地址：http://tzoen.baihongyu.com/