题意:求一个图所有生成树中 最大边与最小边的差的最小值。
解题思路:要求max-min的最小值 就是要让max最小 min 最大。 而我们的kruskal算法求得的当前生成树的max一定是最小的。所以我们只要将min从小到大遍历,然后求得最小值即可。(语言表达的有点绕口,建议参照代码结合着看)。
#include "iostream" #include "algorithm" using namespace std; #define MAXSIZE 6000 #define INF 100000 struct node{ int u; int v; int w; }; node edge[MAXSIZE]; int f[MAXSIZE]; int e; int n,m; void addnode(int u,int v,int w) { edge[e].u=u; edge[e].v=v; edge[e].w=w; e++; } bool cmp(node &a,node &b) { return a.w<b.w; } int findeset(int x) { if(x==f[x]) return x; else return f[x]=findeset(f[x]); } int kruskal(int s) { int i; for (i=1;i<=n;i++) { f[i]=i; } int fnum=n;//集合个数 for (i=s;i<e;i++) { if (findeset(edge[i].u)!=findeset(edge[i].v))//不属于同一集合 { //union f[findeset(edge[i].v)]=findeset(edge[i].u); fnum--; if (fnum==1)//合并完成 { return edge[i].w-edge[s].w; } } } return INF;//无法得到一颗生成树 } int main() { //freopen("in.txt","r",stdin); while(true) { e=0; scanf("%d%d",&n,&m); if ((n==0)&&(m==0)) { break; } int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); addnode(a,b,c); } //求所有生成树中 最大边与最小边差的最小值 max-min 最小 要max 最小 min 最大 //而kruskal 方法中求得的生成树 max一定是最小 所以我们只要min从小到大取值即可 // sort(edge,edge+e,cmp); int ans=INF; for (int i=0;i<e;i++) { int t =kruskal(i); if (t<ans) { ans=t; } } if (ans!=INF) { printf("%d\n",ans); } else { printf("-1\n"); } } return 0; }
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1704752
NULL 博文链接:https://128kj.iteye.com/blog/1707218
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 2763 程序 线段树 LCA 2000MS AC
目录 译者序 第一部分 概 述 第1章 引言 1 1.1 早期的路由功能 2 1.2 ATM与IP 4 1.3 IP交换 6 1.4 路由器IP交换 8 1.5 一个IP交换的标准 9 1.6 结论 10 第2章 TCP/IP、寻址和选路 12 2.1 TCP/IP的历史 12 ...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ题解 个人写法 线段树每个人都不一样
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)