题意简述
求所有生成树中最大边权与最小边权差最小的，输出它们的差值。
显然我们随便跑一个Kruskal可以得到所有生成树中最大边权最小的边。但是最小边权不好保证。注意到n<=100，m <= (n - 1)n/2即m <= 4950，那就暴力一下。对边排好序后，从头枚举每条边作为最小生成树的第一条边，然后往后找边，跑出小于m个生成树，每跑出一个更新答案就行。
一次AC，时间复杂度O（m²），可以通过。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define N 210 #define M 10000000 using namespace std; int n,m; struct qwq { int x,y,val; bool operator < (const qwq &a) const { return val < a.val; } }e[M]; int fa[N],siz[N]; int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } void merge(int x,int y) { if(siz[x] > siz[y]) swap(x,y); siz[y] += siz[x]; fa[x] = y; return; } void pre_fa() { for(int i = 1;i <= n;i++) { fa[i] = i; siz[i] = 1; } return; } int kruskal() { sort(e + 1,e + 1 + m); int tot = 0,ans = 10000000; for(int j = 1;j <= m;j++) { pre_fa(); tot = 0; int maxx = 0; for(int i = j;i <= m;i++) { int x = find(e[i].x),y = find(e[i].y); if(x != y) { merge(x,y); maxx = max(maxx,e[i].val); tot++; } if(tot == n - 1) { ans = min(maxx - e[j].val,ans); break; } } } if(ans == 10000000) return -1; else return ans; } using namespace std; int main() { while(1) { scanf("%d %d",&n,&m); if(n == m && n == 0) break; memset(e,0,sizeof(e)); for(int i = 1;i <= m;i++) { scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].val); } printf("%d ",kruskal()); } return 0; }