uva 1395 - Slim Span poj 3522 Slim Span（最小生成树算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了uva 1395 - Slim Span poj 3522 Slim Span（最小生成树算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1443字，纯文字阅读大概需要3分钟。
内容图文
最近学习了一下 最小生成树 算法。
所谓最小生成树算法，就是给出一个连通图g[ maxn ][ maxn ]， 找出这个连通图的边权和最小的生成图（树）。
可以实现这个目的的算法，我叫它最小生成树算法。kruskal算法就是我学到的一种实现这种功能的算法。
对于kruskal算法的描述以及简单的证明在刘汝佳第二版上已经说得够明白
本题就是求 最小生成树 里面的 最大边权和最小边权 相差最小的最小生成树。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
const int maxn = 105 * 105;
int m,n;
int u[maxn],v[maxn],w[maxn],r[maxn];
int p[maxn];
int cmp(const int i,const int j){
return w[i]<w[j];
}
int find_(int x){
return p[x]==x?x:p[x]=find_(p[x]);
}
int kruskal(int start){
int cnt = 0;
mem(p);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=start;i<m;i++){
int e=r[i];
int x=find_(u[e]);
int y=find_(v[e]);
if(x!=y){
cnt++;
p[x]=y;
}
if(cnt==n-1)
return i;
}
return -1;
}
int main()
{
// freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0&&m==0)
break;
mem(r);mem(u);mem(v);mem(w);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u[i],&v[i],&w[i]);
}
for(int i=0;i<m;i++) r[i]=i;
sort(r,r+m,cmp);
int temp,ans;
temp = kruskal(0);
if(temp==-1){
puts("-1");
continue;
}
else{
int e1=r[0];
int e2=r[temp];
ans=w[e2]-w[e1];
}
for(int i=1;i<m;i++){
temp = kruskal(i);
if(temp!=-1){
int e1=r[i];
int e2=r[temp];
ans=min(ans,w[e2]-w[e1]);
}
}
printf("%d\n",ans);
}
return 0;
}
原文：http://blog.csdn.net/u013382399/article/details/38944493
内容总结
以上是互联网集市为您收集整理的uva 1395 - Slim Span poj 3522 Slim Span（最小生成树算法）全部内容，希望文章能够帮你解决uva 1395 - Slim Span poj 3522 Slim Span（最小生成树算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。