题目大意：给定N个点，M条边，问它的生成树中权值最大的边和权值最小的边的差值最小是多少？
思路：Dijkstra.将M条边排序，然后求最小生成树，然后把（1）这条边去掉，再做最小生成树，然后把（2）这条边去掉……这样比较每次求出的差值取最小值就可以（注意边的数量不能少于n-1）。这里要注意：去掉若干条边之后，可能就没有生成树了，这里一定要注意判断！
code：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f struct node { int x,y,w; }a[10010]; int f[120]; int n,m,ans; bool cmp(node aa,node bb) { return aa.w<bb.w; } int find(int x) { if(f[x] != x) f[x] = find(f[x]); return f[x]; } void dij(int id) { int tot = 0; for(int i=1;i<=n;i++) f[i] = i; int mx = 0; int mi = INF; for(int i=id;i<=m;i++) { int fx = find(a[i].x); int fy = find(a[i].y); if(fx != fy) { if(a[i].w < mi) mi = a[i].w; if(a[i].w > mx) mx = a[i].w; f[fy] =fx; tot++; } } if(tot == n-1) ans = min(ans,mx-mi); } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; ans = INF; for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++) { if(m-i+1 < n-1) break; dij(i); } if(ans == INF) printf("-1\n"); else printf("%d\n",ans); } return 0; }