题目链接http://poj.org/problem?id=3522
kruskal+并查集，注意特殊情况比如1,0 、0,1、1,1
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
#define MAXN 5005
struct edge{
int u,v,cost;
};
int comp(const edge& e1,const edge& e2){
return e1.cost<e2.cost;
}
edge es[MAXN];
int V,E;
int par[MAXN],rank[MAXN];
void init(){
for(int i=;i<=V;i++){
par[i]=i;
}
}
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
par[x]=y;
}
}
bool same(int x,int y){
return find(x)==find(y);
}
int kruskal(int k){
init();
int min,max=-;
int esum=;
for(int i=k;i<E;i++){
if(E-k<V-)break;
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
esum++;
max=max<e.cost?e.cost:max;
}
if(esum==V-){
min=es[k].cost;
return max-min;
}
}
return -;
}
int main()
{
int i,flag=;
while(scanf("%d%d",&V,&E)==){
if(V==&&E==)break;
for(i=;i<E;i++){
scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);
}
if(E==||V>||E<V-){
printf("-1\n");continue;}
sort(es,es+E,comp);
int min=INT_MAX,x;
for(i=;i<E-V+;i++){
x=kruskal(i);
if(min>x&&x!=-){
min=x;
}
}
if(min!=INT_MAX)
printf("%d\n",min);
else
printf("-1\n");
}
return ;
}