此题对kruskal算法做了变形,不是求最小生成树,而是求最大边权值与最小边权值之差最小的生成树,同样可以用kruskal算法的实现方法,采用并查集。如果求最小生成树要将边加入到堆中,并且不需要遍历所有的生成树情况
//此题对kruskal算法做了变形,不是求最小生成树 //而是求最大边权值与最小边权值之差最小的生成树 //同样可以用kruskal算法的实现方法,采用并查集 #include <iostream> #include <stdlib.h> #include <algorithm> #define inf 10000000//边权值的上界 using namespace std; int m,n; //p数组用于记录父节点,r数组用于统计以r为根的子 //树中间有多少个点,其实r数组可以取消,因为 //直接由根节点的绝对值就可以这个集合中的元素个数 int p[105]; int r[105]; struct edge{ int u; int v; int w; }e[5000]; bool cmp(const edge & e1,const edge & e2){ return e1.w < e2.w; } void set_init(){//并查集初始化 for (int i = 1;i <= n;i++) { p[i] = i; r[i] = 1;//初始状态每个的根是自己,集合个数为1 } } // int set_find(int x){//查找包含x的集合树的根 // while (p[x] >= 0) // { // x = p[x]; // } // return x; // } //以上为非递归实现,递归实现如下 int set_find(int x){ if(p[x] == x) return x; else p[x] = set_find(p[x]); return p[x]; } // void set_union(int root1,int root2){//将两个集合合并 // p[root1]+=p[root2]; // p[root2] = root1;//用根root2连接到root1下面 // } //为防止树的退化,改进版的union操作如下 void set_union(int x,int y){//将两个集合合并 if(r[x] <= r[y]){ p[x] = y; r[y]+=r[x];//y作为根 } else { p[y] = x; r[x]+=r[y]; } } int main(){ int i,j,k,ans,px,py,a,b,temp; while (cin>>n>>m) { if (n == 0 && m == 0) break; for (i = 0;i < m;i++) { cin>>e[i].u>>e[i].v>>e[i].w; } if ( n == 2 && m == 1) { cout<<"0"<<endl;//2点1边的情况单独处理 continue; } sort(e,e+m,cmp); ans = inf; for (i = 0; i<m;i++) { k = 0; set_init(); for (j = i;j<m;j++) { px = set_find(e[j].u); py = set_find(e[j].v); if (px != py) { set_union(px,py);//注意这里只是求生成树,不一定是mst,只要不在同一个集合中就可以选这条边,两个端点变成同一个集合内 k++; if(k == 1){//这是最小的边 a = e[j].w; } else if (k == n-1)//这是最大的边也是最后一条边 { b = e[j].w; temp = b - a; if (temp < ans) { ans = temp; } break; } } } } if (ans == inf) { cout<<"-1"<<endl; } else cout<<ans<<endl; } return 0; }
您还没有登录,请您登录后再发表评论
NULL 博文链接:https://128kj.iteye.com/blog/1707218
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
这份代码用C++实现了经典算法并查集,来源于poj题目1182
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ中级-基本算法 解题报告+AC代码
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
poj 1611 The Suspects 代码 并查集的应用
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
POJ1089 并查集可以解决 并查集加路径压缩
关于C++ 算法 北大网站POJ 八数码问题
供初学编程基本算法的人练习使用,在poj.grids.cn上
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1707218
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
这份代码用C++实现了经典算法并查集,来源于poj题目1182
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ中级-基本算法 解题报告+AC代码
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
poj 1611 The Suspects 代码 并查集的应用
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
POJ1089 并查集可以解决 并查集加路径压缩
关于C++ 算法 北大网站POJ 八数码问题
供初学编程基本算法的人练习使用,在poj.grids.cn上