首页 > 代码库 > 【kruscal】【最小生成树】poj3522 Slim Span
【kruscal】【最小生成树】poj3522 Slim Span
求一个生成树,使得最大边权和最小边权之差最小。由于数据太小,暴力枚举下界,求出相应的上界。最后取min即可。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int n,m,fa[101],rank[101]; 6 void clear(){for(int i=1;i<=n;i++) fa[i]=i; memset(rank,0,sizeof(rank));} 7 int findroot(int x) 8 { 9 if(fa[x]==x) return x;10 int rt=findroot(fa[x]);11 fa[x]=rt;12 return rt;13 }14 void Union(int U,int V)15 {16 if(rank[U]<rank[V]) fa[U]=V;17 else18 {19 fa[V]=U;20 if(rank[U]==rank[V]) rank[U]++;21 }22 }23 struct Edge{int u,v,w;};24 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}25 Edge edges[5001];26 int tot,ans,maxv;27 int main()28 {29 while(1)30 {31 scanf("%d%d",&n,&m);32 if(!n) break;33 for(int i=1;i<=m;i++) scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);34 sort(edges+1,edges+m+1,cmp); ans=2147483647;35 for(int j=1;j<=m;j++)36 {37 tot=0; clear();38 for(int i=j;i<=m;i++)39 {40 int f1=findroot(edges[i].u),f2=findroot(edges[i].v);41 if(f1!=f2) {Union(f1,f2); tot++; if(tot==n-1) {maxv=edges[i].w; goto WIN;}}42 }43 continue;44 WIN:ans=min(ans,maxv-edges[j].w);45 }46 printf("%d\n",ans!=2147483647 ? ans : -1);47 }48 return 0;49 }
【kruscal】【最小生成树】poj3522 Slim Span
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。