- 浏览: 601684 次
- 来自: ...
文章分类
最新评论
-
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 3747题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1659POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3055POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1479POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1929题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1642关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1871关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1880POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1899POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1766POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1647分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2253接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1544关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1397接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1828关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1821关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1819关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2104POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1347问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2152在http://poj.org/上用JAVA解题一般用 ...
相关推荐
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
* 最小生成树算法:最小生成树算法是指计算图的最小生成树的算法,如 prim、kruskal。 * 拓扑排序:拓扑排序是指计算图的拓扑排序的算法,如 poj1094。 * 二分图的最大匹配:二分图的最大匹配是指计算二分图的最大...
根据提供的文件信息,我们可以将POJ练习题中的算法进行分类,并对每一类中的知识点进行详细的阐述。POJ(Pacific Ocean Judge)是一个在线编程平台,它提供了丰富的编程题目,旨在帮助学习者掌握各种基础算法和数据...
【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...
【北大POJ初级-图算法】是一系列针对北京大学在线编程平台POJ(Problem Online Judge)上的初级编程题目,重点在于图论算法的应用。这个解题报告集合了多种图算法的实现,帮助学习者掌握如何在实际问题中运用这些...
POJ是中国北京大学维护的一个在线编程练习系统,提供了大量的编程题目供参赛者练习。 【描述】提到的"poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究"表明这份压缩包内包含的是对POJ平台上...
在编程竞赛领域,POJ(Programming Online Judge)是一个广受欢迎的在线编程平台,它提供了许多题目供参赛者解决,以提升编程和算法能力。本文主要关注的是“POJ中级图算法”的一系列题目及其解题报告和AC(Accepted...
【poj 2485 Highways 测试数据】是一个编程竞赛题目,源自著名的在线算法竞赛平台POJ(Programming Online Judge)。此题目的主要目的是通过解决实际问题来考察参赛者的图论和算法设计能力,特别是涉及到最小生成树...
对于POJ第1861题,参赛者可能需要读取输入数据,构建一个加权图,然后应用Prim或Kruskal算法找出最小生成树,最后输出树中边的权重总和或者某种特定格式的树结构。解题过程可能涉及到错误处理、边界条件检查以及效率...
在本压缩包“poj算法题目实现.zip”中,包含了五个经典的编程竞赛题目,主要针对的是POJ(Programming Online Judge)平台。这些题目是程序员提升算法能力、锻炼编程技巧的重要资源。下面,我们将详细探讨每个题目...
* 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:例如 poj1094。 * 二分图的最大匹配:例如 poj3041、poj3020。 * 最大流的增广路算法:例如 poj1459、poj3436。...
ACM常用算法及其相应的练习题 本资源总结了 ACM 竞赛中常用的算法和相应的练习题,涵盖了基础算法、图算法、数据结构、搜索、动态规划和数学等方面的知识点。 一、基础算法 * 枚举:poj1753, poj2965 * 贪心:poj...
标题 "POJ 1751 求最小生成树Prim算法(JAVA)" 提到的是一个编程挑战,涉及图论中的经典算法——Prim算法。在计算机科学中,Prim算法是用于寻找加权无向图的最小生成树的一种有效方法。最小生成树是一棵树形结构,...
- 最小生成树算法:如Prim算法和Kruskal算法,用于找出图中的最小生成树,如`poj1789, poj2485`。 - 拓扑排序:适用于有向无环图,用于确定任务的执行顺序,如`poj1094`。 - 二分图的最大匹配:如匈牙利算法,...
- (poj1789, poj2485, poj1258, poj3026):介绍普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal),用于寻找加权无向图的最小生成树。 4. **拓扑排序**: - (poj1094):适用于有向无环图(DAG)的一种排序方式,...
2. **最小生成树**:Prim算法和Kruskal算法,用于构建图的最小生成树(poj1789, poj2485, poj1258, poj3026)。 3. **网络流**:Max-flow算法,用于解决最大流问题(poj1094)。 4. **拓扑排序**:解决有向无环图的...
标题中的“POJ 1078 算法”指的是北京大学在线判题系统(Problem Online Judge,简称POJ)中的第1077题,这通常是一个编程竞赛或者算法练习题目。POJ是一个供程序员练习算法、提交代码并获取运行结果的平台,主要...
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ算法分类和题目推荐指南 本资源主要介绍了POJ(Online Judge)平台上各种算法分类和推荐题目,涵盖了动态规划、模拟、博弈等多种类型。以下是详细的知识点说明: 一、动态规划 动态规划是一种非常重要的算法...