#include<iostream>
#include<algorithm>
using namespace std;
struct edge
{   int from;
	int end;
	int length;
} E[5000];
int Eindex[5000];//保存边的编号
int n,m;//顶点数目，和边数
int p[101];//记录某个点的父亲节点
int find(int i) {return p[i]==i?i:p[i]=find(p[i]);}//查找i好节点所在的集合的代表元
int cmp(const void *a,const void*b) {return E[(*(int*)a)].length- E[(*(int*)b)].length;}
int main()
{   while(cin>>n>>m)
	{
		if(n==0&&m==0)break;
		int i=0,j=0;
		for(i=1;i<=m;i++)
		{ cin>>E[i].from>>E[i].end>>E[i].length; Eindex[i]=i; }
        qsort(Eindex+1,m,sizeof(Eindex[1]),cmp); //对变得编号排序
		int ans=20050;
		for(i=1;i<=m&&(m-(i-1))>=n-1;i++)//从第i小的边开始 执行克鲁斯卡尔算法
		{   for(j=0;j<=n;j++)p[j]=j;//初始化p数组
			int esum=0;//记录已经找了多少条边了
			int emax=0;//记录这次求最小生成树的最大边
			for(j=i;j<=m;j++)
			{   if(esum+(m-(j-1))<n-1||esum==n-1)break;
				int index=Eindex[j];
				int x=find(E[index].from);
				int y=find(E[index].end);
				if(x!=y)//如果两个顶点不在同一个集合（或在说不在同一个连通分量中）
				{   p[x]=y;  //合并两个集合，
					esum++;
					emax=E[index].length;
				}
			}
			if(esum==n-1)//说明得到一个最小生成树
			{       if(emax-E[Eindex[i]].length<ans)
					ans=emax-E[Eindex[i]].length;
			}
			if(ans==0)break;
		}
		if(ans!=20050)
			 cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

• Re:传统做法，枚举最小边，多次执行克鲁斯卡尔算法，49行的AC代码 (1429) pojonly 2011-03-22 21:27:58