题目链接:http://poj.org/problem?id=3522思路:题目要求最小生成树中最大边与最小边的最小差值,由于数据不是很大,我们可以枚举最小生成树的最小边,然后kruskal求最小生成树,直到不能生成生成树为止,然后取最小的差值即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
#define inf 1<<30 struct Edge{
int u,v;
int len;
}edge[MAXN*MAXN];
int parent[MAXN];
int n,m; void Initiate()
{
for(int i=;i<=n;i++){
parent[i]=i;
}
} int Find(int x)
{
if(x==parent[x]){
return parent[x];
}
parent[x]=Find(parent[x]);
return parent[x];
} void Union(int u,int v)
{
int r1=Find(u),r2=Find(v);
if(r1==r2)return ;
parent[r1]=r2;
} int cmp(const Edge &p,const Edge &q)
{
return p.len<q.len;
} int Kruskal(int id)
{
int count=,MIN=inf,MAX=-inf;
for(int i=;i<m;i++){
if(edge[i].len<edge[id].len)continue;
int u=edge[i].u,v=edge[i].v;
if(Find(u)!=Find(v)){
MIN=min(MIN,edge[i].len);
MAX=max(MAX,edge[i].len);
count++;
Union(u,v);
if(count==n-)return MAX-MIN;
}
}
return -;
} int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==&&m==)break;
for(int i=;i<m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].len);
}
sort(edge,edge+m,cmp);
int ans=inf;
for(int i=;i<m;i++){
Initiate();
int tmp=Kruskal(i);
if(tmp==-)break;
ans=min(ans,tmp);
}
if(ans!=inf){
printf("%d\n",ans);
}else
printf("-1\n");
}
return ;
}