题意描述

某国有$n$个村子，$m$条道路。

为了实现“村村通工程”现在要”油漆”$n-1$条道路（因为某些人总是说该国所有的项目全是从国外进口来的，只是漆上本国的油漆罢了）。

因为“和谐”是此国最大的目标和追求，以致于对于最小造价什么的都不在乎了，只希望你所选出来的最长边与最短边的差越小越好。

输入格式

第一行给出一个数字$t$，代表有多少组数据。

对于每组数据，首先给出$n$ , $m$

下面M行，每行三个数$a,b,c$代表$a$村与$b$的村道路距离为$c$.

输出格式

输出仅有一行，为最小差值,如果无解输出-1.

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于$100\%$的数据$2 ≤ n ≤ 100$,$0 ≤ m ≤ \frac{n \times (n − 1)}{2}$

每条边的权值小于等于$10^4$

保证没有自环与重边

分析

真的是签到题了……

首先，题目中告诉我们要在$n$个点中选出$n-1$条边，自然而然的能想到最小生成树。

再看这个极小的数据范围，自然是怎么暴力怎么来。

我们把所有边加进图中，排一遍序，之后枚举长度最小的边，将比它小的边都忽略跑最小生成树即可。

时间复杂度为$O(m^2)$，由于本题数据范围较小，足以通过。

听说如果数据大的话可以使用$LCT$维护，~~但我不会~~。

剩下的见代码。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 10001

using namespace std;

int t , n , m;

struct Edge{
    int from;
    int to;
    int last;
    ll dis;
}edge[N << 1];

int head[N << 1];
int edge_num;

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = (Edge){from , to , head[from] , dis};
    head[from] = edge_num;
}

int pre[N << 1];

int find(int root){
    if(pre[root] == root){
        return root;
    }
    else{
        return pre[root] = find(pre[root]);
    }
}

I bool cmp(Edge a , Edge b){
    return a.dis < b.dis;
}

ll maxn = -1;

bool Kruskal(int k){
    for(int i = 1; i <= n; i ++){
        pre[i] = i;
    }    
    ll num = 0;
//    sort(edge + 1 , edge + 1 + m , cmp);
    for(int i = k; i <= m; i ++){
        int l = find(edge[i].from) , r = find(edge[i].to);
        if(l == r){
            continue;
        }
        pre[l] = r;
        maxn = max(maxn , edge[i].dis);
        num ++;
        if(num == n - 1){
            return true;
        }
    }
    return false;
}


int main(){
    int u , v , d;
    scanf("%d" , &t);
    while(t --){
        scanf("%d%d" , &n , &m);
        for(int i = 1; i <= m; i ++){
            scanf("%d%d%d" , &u , &v , &d);
            add_edge(u , v , d);
        }
        sort(edge + 1 , edge + 1 + m , cmp);
        ll ans = 0x3f3f3f3f;
        for(int i = 1; i <= m; i ++){
            if(Kruskal(i)){
                if(ans > maxn - edge[i].dis){
                    ans = maxn - edge[i].dis;
                }
            }
        }
        printf("%lld\n" , (ans == 0x3f3f3f3f ? -1 : ans) ) ;
        for(int i = 1; i <= m; i ++){
            head[i] = edge[i].from = edge[i].to = edge[i].dis = edge[i].last = 0;
        }
        edge_num = 0;
        maxn = -1;
    }
    return 0;
}