poj 3522 Slim Span (Kruskal+枚举) (二)
,&spantree[i].y,&spantree[i].s);
}
qsort(spantree,m,sizeof(spantree[0]),comp); //把边从小到大排序
for(i=0,end=0,start=0,min=INF;i
{
Empty(n);
for(j=i,num=0;j
{
if(Find(spantree[j].x)!=Find(spantree[j].y))
{
Union(spantree[j].x,spantree[j].y);
num++; //某个生成树的第num条边
if(num==1) //第一条最小，num-1条最大
start=spantree[j].s;
if(num==n-1) //易错点**：是if不是else if,因为可能只有一条边
end=spantree[j].s;
}
if(num==n-1)
{
a=end-start;
if(a
{
min=a; //找到最小的差值
}
break;
}
}
}
if(min!=INF) printf("%d\n",min);
else printf("-1\n");
}
return 0;
}