学步园

                                  想看更多的解题报告:
http://blog.csdn.net/wangjian8006/article/details/7870410
                                     转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：有N个节点，M条无向边的一个图，求在这个图中所有的生成树中，权值最大边减去权值最小边的最小值，如果不能构成一颗生成树没有就输出-1
解题思路：由于N与M都不大，所以对M条边排序后枚举边的起始点，kruscal后看能不能构成一颗生成树，可以的话判断最大边-最小边

/*
Memory 232K
Time   94MS
*/
#include <iostream>
using namespace std;
#define MAXM 5000
#define MAXV 105
#define inf 1<<29

typedef struct{
	int s,t,w;
}Edge;

Edge edge[MAXM];
int n,m,ans,set[MAXV];

int find(int x){
	if(x==set[x])
		return x;
	else{
		int rt=find(set[x]);
		set[x]=rt;
		return set[x];
	}
}

bool TUnion(int a,int b){
	int fa=find(a);
	int fb=find(b);
	if(fa==fb) return false;
	set[fb]=fa;
	return true;
}

void kruskal(int start){
	int i,min=inf,max=-1,s,t,w,cnt=0;

	for(i=0;i<=n;i++) set[i]=i;
	
	for(i=start;i<m;i++){
		s=edge[i].s;
		t=edge[i].t;
		w=edge[i].w;
		if(TUnion(s,t)){
			if(w<min) min=w;
			if(w>max) max=w;
			cnt++;
			if(cnt==n-1) break;
		}
	}
	if(cnt!=(n-1)) return ;
	if(ans>max-min) ans=max-min;
}

int cmp(const void *a,const void *b){
	return (*(Edge *)a).w-(*(Edge *)b).w;
}

bool work(){
	int i;
	ans=inf;
	kruskal(0);
	if(ans==inf) return false;
	for(i=1;i<m;i++) kruskal(i);
	return true;
}

int main(){
	int i;
	while(scanf("%d%d",&n,&m) && (n || m)){
		for(i=0;i<m;i++) scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].w);
		qsort(edge,m,sizeof(edge[0]),cmp);
		if(!work()) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}