UVA 1395 (kruskal)

时间:2023-11-13 21:29:14
/*

    最大路与最小路的问题:
这道题看似简单,但是若不知道思路将无法写出。 思路:最小生成树很容易求出,但是最大值与最小值只差很难保证是最小的,
比如:1 5 5 6 100 101
很明显101 - 5 < 100 - 1
所以:只需要枚举到m条边的情况就行。
*/ #include<iostream>
#include<algorithm>
#include<cstdio> using namespace std; class kruskal
{
public:
int a,b,value;
}edge[]; int n,m; int f[];//并查集
int s[];//根的数目 int ans; bool cmp(kruskal a,kruskal b)
{
return a.value < b.value;
} int Find(int x)
{
if(f[x] == x)
return x;
else
f[x] = Find(f[x]);
return f[x];
} int Union(int x,int y)
{
int a = Find(x);
int b = Find(y);
if(a == b)
return ;
else if(s[a] <= s[b]){ //使用了优化并查集
f[a] = b;
s[b] += s[a];
}
else {
f[b] = a;
s[a] += s[b];
}
return ;
} int kruskal(int i)
{
int pos = ;
int r;
for( ;i <= m; i++){
if(Union(edge[i].a,edge[i].b)){
pos++;
if(pos == )
r = edge[i].value;
if(pos == n - ){
ans =min(ans,edge[i].value - r);
}
}
}
return ans;
} int main()
{
//freopen("in.txt","r",stdin);
while(cin>>n>>m){
if(n == && m == )
break;
for(int i = ;i <= m; i++)
cin>>edge[i].a>>edge[i].b>>edge[i].value;
ans = ;
sort(edge+,edge+m+,cmp);
for(int i = ;i <= m - n + ; i++){
for(int j = ;j <= n; j++) {
f[j] = j;
s[j] = ;
}
ans = kruskal(i);
}
if(ans == ){
printf("-1\n");
}
else
printf("%d\n",ans);
}
return ;
}