记录编号	487804	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	最小差异值	最终得分	100
用户昵称	Kyru Yann	是否通过	通过
代码语言	C++	运行时间	1.683 s
提交时间	2018-02-12 11:35:07	内存使用	2.64 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <cctype>
#include <iomanip>
#define inf 0x7f7f7f7f
using namespace std;
int first[50005],last[50005],node,n,m,fa[50005],ans=inf;
bool done[50005];
struct edge
{
	int from;
	int to;
	int next;
	int w;
	friend bool operator < (edge a,edge b)
	{
		return a.w<b.w;
	}
}e[200005];
void addedge(int u,int v,int w)
{
	e[++node]=(edge){u,v,0,w};
	if(first[u]==0) first[u]=node;
	else e[last[u]].next=node;
	last[u]=node; return;
}
void init()
{
	int f,t,w;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&f,&t,&w);
		e[++node]=(edge){f,t,0,w};
	}
	sort(e+1,e+1+m);
}
void init_UF()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	return;
}
int find(int x)
{
	if(fa[x]==x) return x;
	int pa=find(fa[x]);
	fa[x]=pa;
	return fa[x];
}
bool judge(int x,int y)
{
	return find(x)==find(y);
}
void merge(int x,int y)
{
	int rx=find(x),ry=find(y);
	if(rx!=ry) fa[rx]=ry;
	return;
}
/*
最优生成树
枚举最小边，用大于等于最小边的边做最大生成树；当图不连通后退出 
时间复杂度O(m^2) 
*/
int best_spt(int s,int mine)
{
	int minn=inf,maxn=-inf,cnt=0;
	init_UF();
	for(int i=mine;i<=node;i++)
	{
		if(judge(e[i].from,e[i].to)) continue;
		else merge(e[i].from,e[i].to);
		minn=min(minn,e[i].w);
		maxn=max(maxn,e[i].w);
		cnt++;
		if(cnt==n-1) break;
	}
	if(cnt!=n-1) return -1;
	return maxn-minn;
}
int main()
{
	freopen("dvalue.in","r+",stdin);
	freopen("dvalue.out","w+",stdout);
	init();
	for(int i=1;i<=node;i++)
	{
		int t=best_spt(1,i); 
		if(t==-1) break;
		else ans=min(t,ans);
	}
	printf("%d\n",ans);
	return 0;
}