- 浏览: 583826 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
克鲁斯卡尔kruskal 算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:
先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至子图中含有 n-1条边为止。
POJ1679:The Unique MST
题意:给一个无向图,判断这个图的最小生成树MST是否是唯一的。如果是唯一的,输出最小生成树的权值,如果不是唯一的,输出“Not Unique!”
分析:先求出一棵最小生成树,记下最小权值为mst.然后枚举树上的每条边,去掉以后再求一次最小生成树,只要出现权值等于mst,那么最小生成树一定不唯一.
样例:
Sample Input
2(测试次数)
3 3(顶点和边的数目)
1 2 1(一条边的两个顶点和权值,以下同)
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!
AC代码:
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:
先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至子图中含有 n-1条边为止。
POJ1679:The Unique MST
题意:给一个无向图,判断这个图的最小生成树MST是否是唯一的。如果是唯一的,输出最小生成树的权值,如果不是唯一的,输出“Not Unique!”
分析:先求出一棵最小生成树,记下最小权值为mst.然后枚举树上的每条边,去掉以后再求一次最小生成树,只要出现权值等于mst,那么最小生成树一定不唯一.
样例:
Sample Input
2(测试次数)
3 3(顶点和边的数目)
1 2 1(一条边的两个顶点和权值,以下同)
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!
AC代码:
import java.util.Scanner; import java.util.Arrays; public class Main{ private int father[]; //记录顶点的父节点 private Edge e[]; //图的所有边 private int n;//结点个数 private int l;//边的数目 private int mst;//最小生成树的最小权值 private boolean uni;//最小生成树是否唯一的标志 public Main(int n,int l,Edge[] e){ this.n=n; this.l=l; this.e=e; father=new int[n+1]; mst=0; uni=true; make_set(); } private void make_set(){//将每个顶点初始化为一个集合(树),父节点指向自己。 for( int x = 1; x <= n; x ++) father[x] = x; } private int find_set(int x){//找x的父节点 if(x != father[x]) father[x] = find_set(father[x]);//路径压缩 return father[x]; } public int getMst(){ return this.mst; } public boolean getUni(){ return this.uni; } private void kruskal(){ int x, y; int mst_e[]=new int[n];//用于记录第一次krushal得到的MST的边 int edge_num=0;//第一次krushal后的边数; int k = 0; // 下面为第一次kruskal求MST。 make_set(); Arrays.sort(e);//将边按权值排序(从小到大) for(int i = 0; i < l; i ++){ x = find_set(e[i].a); y = find_set(e[i].b); if(x != y){ father[y] = x;//合并两棵树 mst += e[i].weight; mst_e[k ++] = i; // 记录下MST的边。 } } edge_num = k;// 记录MST的边的数目 for(int r = 0; r < edge_num; r ++){//枚举树上的每条边,去掉以后再求一次最小生成树, make_set(); // 每次kruskal要记得初始化并查集。 int sec_mst=0;//用于记录下面求出的最小生成树的最小权值 int num = 0; for(int i = 0; i < l; i ++){ if(i == mst_e[r]) continue; // 模拟删边。 x = find_set(e[i].a); y = find_set(e[i].b); if(x != y){ father[y] = x; sec_mst += e[i].weight; num ++; } } if(num != edge_num) continue; //判断是能构成完整的次小生成树。 if(sec_mst == mst){ //System.out.println(mst); //如果能构造成完整的次小生成树,并且次小生成树的值与mst相等,则说明MST不唯一。 uni = false; return; } } } public static void main(String args[]){ Scanner in=new Scanner(System.in); int t=in.nextInt(); while(t -->0){ int n=in.nextInt();//顶点数 int m=in.nextInt();//边数 Edge[] e=new Edge[m]; for(int i = 0; i <m; i++){ e[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt()); } Main ma=new Main(n,m,e); ma.kruskal(); if(!ma.getUni()) System.out.printf("Not Unique!\n"); else System.out.printf("%d\n", ma.getMst()); } } } class Edge implements Comparable { int a; //边的一个顶点,从数字0开始 int b; //边的另一个顶点 int weight; //权重 Edge(int a,int b,int weight){ this.a=a; this.b=b; this.weight=weight; } @Override public int compareTo(Object o){ Edge m = (Edge)o; int result=(int)(this.weight - m.weight); if(result>0) return 1; else if(result==0) return 0; else return -1; } }
- Main1679.zip (1.5 KB)
- 下载次数: 1
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3660题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2981POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1848题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1563分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1353接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1672关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1748关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2021POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1285问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2100在http://poj.org/上用JAVA解题一般用 ...
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
用贪心算法解决POJ 1065的木棍处理问题
关于C++ 算法 北大网站POJ 八数码问题
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ中级-基本算法 解题报告+AC代码
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
poj1087贪心算法实验报告 poj1087贪心算法实验报告
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为: