记录编号	488131	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	最小差异值	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	2.891 s
提交时间	2018-02-17 21:24:23	内存使用	1.04 MiB

#include<iostream>  
#include<cstdio>  
#include<cctype>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
const int maxn=5001;  
const int maxm=50001;  
struct edge
{  
    int u,v,w;  
}
e[maxm<<1];   
int n,m,fa[maxn],eid=0;  
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}  
void merge(int a,int b)
{  
    a=get(a),b=get(b);  
    if(a!=b) 
	{
	    fa[a]=b;
	}  
}  
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}  
inline int read()
{  
    int s=0,f=1;  
    char c=getchar();  
    while(!isdigit(c))
	{  
        if(c=='-') f=-1;  
        c=getchar();  
    }  
    while(isdigit(c))
	{  
        s=s*10+c-48;  
        c=getchar();  
    }  
    return s*f;  
}  
int res=999999;  
void init()
{  
    for(int i=1;i<=n;i++) 
	fa[i]=i;  
}  
int main()
{ 
    freopen("dvalue.in","r",stdin);        
    freopen("dvalue.out","w",stdout);      
    while(scanf("%d%d",&n,&m)==2&&n)
	{  
        int a,b,c;  
        eid=0,res=999999;      
        for(int i=1;i<=m;i++)  
        {  
            a=read();b=read();c=read();  
            e[++eid].u=a;e[eid].v=b;e[eid].w=c;  
        }  
        sort(e+1,e+m+1,cmp);   
        for(int k=1;k<=m-n+2;k++)
        {  
            init();  
            int rst=n;  
            for(int i=k;i<=m;i++)    
            {        
                int x=e[i].u;int y=e[i].v;  
                if(get(x)!=get(y))
				{  
                    merge(x,y);  
                    rst--;  
                }    
                if(rst==1)
			    {  
                    res=min(e[i].w-e[k].w,res);  
                    break;  
                } 
            }  
        }  
        if(res!=999999) 
        {
	        cout<<res; 
	    }
    }  
    return 0;  
}