poj 3522 Slim Span：枚举+最小生成树

2016年07月27日 38 阅读

poj 3522 Slim Span：枚举+最小生成树2014-12-06链接：http://poj.org/problem？id=3522题目：Slim SpanTime Limit: 5000MSMemory Limit: 65536KTotal Submissions: 4962Accepted: 2587DescriptionGiven an undirected weighted graph G, you should find one of s...

poj 1679 The Unique MST：次小生成树

2016年07月27日 44 阅读

poj 1679 The Unique MST：次小生成树2014-12-06链接：http://poj.org/problem？id=1679题目：DescriptionGiven a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 （Spanning Tree）: Consider a connected, undirected ...

poj 2912 Rochambeau

2016年07月27日 38 阅读

poj 2912 Rochambeau2014-12-06链接:http://poj.org/problem？id=2912题目：DescriptionN children are playing Rochambeau （scissors-rock-cloth） game with you. One of them is the judge. The rest children are divided into three groups （it is po...

poj 1182 食物链：经典！种类并查集

2016年07月27日 35 阅读

poj 1182 食物链：经典！种类并查集2014-12-06链接：http://poj.org/problem？id=1182原题：Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y...

poj 1703 Find them, Catch them：种类并查集

2016年07月27日 34 阅读

poj 1703 Find them, Catch them：种类并查集2014-12-06链接：http://poj.org/problem？id=1703题目：Find them, Catch themTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 22289Accepted: 6648DescriptionThe police office in Tadu City decides t...

poj 1733 Parity game：带权并查集

2016年07月27日 35 阅读

poj 1733 Parity game：带权并查集2014-12-06链接：http://poj.org/problem？id=1733题目：DescriptionNow and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuou...

poj 1611 The Suspects：并查集

2016年07月27日 36 阅读

poj 1611 The Suspects：并查集2014-12-06链接：http://poj.org/problem？id=1611题目：The SuspectsTime Limit: 1000MSMemory Limit: 20000KTotal Submissions: 15926Accepted: 7622DescriptionSevere acute respiratory syndrome （SARS）, an atypical pneumo...

HDU 2818 Building Block, poj 1988 Cube Stacking：带权并查集

2016年07月27日 41 阅读

HDU 2818 Building Block, poj 1988 Cube Stacking：带权并查集2014-12-06链接:HDU: http://acm.hdu.edu.cn/showproblem.php？pid=2818POJ: http://poj.org/problem？id=1988题目：Problem DescriptionJohn are playing with blocks. There are N blocks （1 <...

poj 1456 Supermarket：贪心， 并查集

2016年07月27日 39 阅读

poj 1456 Supermarket：贪心， 并查集2014-12-06链接：http://poj.org/problem？id=1456题目：DescriptionA supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an ...

HDU 3038 How Many Answers Are Wrong？ ：带权并查集

2016年07月27日 43 阅读

HDU 3038 How Many Answers Are Wrong？ ：带权并查集2014-12-06链接：http://acm.hdu.edu.cn/showproblem.php？pid=3038题目：Problem DescriptionTT and FF are ... friends. Uh... very very good friends -________-bFF is a bad boy, he is always wooing TT...

内部排序：插入排序和希尔排序的N种实现

2016年07月27日 36 阅读

内部排序：插入排序和希尔排序的N种实现2014-12-06前言本来想将所有的内部排序总结为一篇博文，但是随着研究的深入，还是放弃了这个念头，斟前酌后，还是觉得分开来写比较好，具体原因，看完本篇博文也就自然明了了。本篇文章主要探讨插入排序和希尔排序，之所将二者放在一起，很明显，是因为希尔排序是建立在插入排序的基础之上的。注：以下各排序算法的N种实现方法大部分都是我根据算法思想，自己写出来的，或者是参考其本身的经典实现，我自己都已测试通过，但不敢保证一定都没问...

内部排序：冒泡排序和选择排序

2016年07月27日 37 阅读

内部排序：冒泡排序和选择排序2014-12-06前言之所以把冒泡排序和选择排序放在一起，是因为二者的实现代码很相似，而且都是最基本的排序方式，非常容易理解和实现。当然，如果仅仅是为了讲述这两种排序方式，那也根本没必要写这篇博文了。和上篇博文一样，我会在冒泡排序和选择排序原始代码的基础上给出一些改进和优化，这才是本文的重点所在。原始冒泡排序冒泡排序的思想很简单，如果要求排序后序列中元素按照从小到大的顺序排列，则冒泡排序的步骤如下：1、依次比较序列中相邻的两个...

内部排序：堆排序

2016年07月27日 35 阅读

内部排序：堆排序2014-12-06 未知 前言堆排序、快速排序、归并排序（下篇会写这两种排序算法）的平均时间复杂度都为O（n*logn）。要弄清楚堆排序，就要先了解下二叉堆这种数据结构。本文不打算完全讲述二叉堆的所有操作，而是着重讲述堆排序中要用到的操作。比如我们建堆的时候可以采用堆的插入操作（将元素插入到适当的位置，使新的序列仍符合堆的定义）将元素一个一个地插入到堆中，但其实我们完全没必要这么做，我们有执行操作更少的方法，后面你会看到，我们基本上只用到...

内部排序：归并排序和快速排序

2016年07月27日 34 阅读

内部排序：归并排序和快速排序2014-12-06前言 之所以把归并排序和快速排序放在一起探讨，很明显两者有一些相似之处：这两种排序算法都采用了分治的思想。下面来逐个分析其实现思想。归并排序实现思想归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。归并排序中一般所用到的是2-路归并排序，即将含有n个元素的序列看成是n个有序的子序列，每个子序列的长度为1，而后两两合并，得到n/2个长度为2或1的有序子序列，再进行两两合并。。。直到最后由两个...

内部排序：计数排序、基数排序和桶排序

2016年07月27日 37 阅读

内部排序：计数排序、基数排序和桶排序2014-12-06前言最后三种排序算法了，由于都不是基于比较的排序，因此这三种排序算法可以以线性时间运行。但是因为限制条件的特殊性，因此应用面没有基于元素比较的排序算法广，但是在很多特定的情况下还是蛮有用途的，而且效率极高。计数排序计数排序是建立在这样的前提条件下的：假设n个输入元素的每一个都是0到k区间内的一个整数，其中k为某个整数。因此我们后面所写的程序也只是针对0到k之间的元素进行排序，换句话说，排序元素中不能有...

博弈树，动态规划（计算好的子问题存储起来，以后直接取用）

2016年07月27日 36 阅读

博弈树，动态规划（计算好的子问题存储起来，以后直接取用）2014-12-10 csdn博客 u010026901public class GameTree {/*** 判断剩余球数，谁能取到最后谁赢，* ，一人取一次，默认我方先取，，能否必胜，能就返回true，否则false* @param x剩余球数* @return*/static boolean f（int x）{int[] op={1,3,7,8};//每次取球只能有四种情况for（int i=0...

Dijkstra求含权图最短通路；试探与回溯保证枚举的不遗漏不重复

2016年07月27日 34 阅读

Dijkstra求含权图最短通路；试探与回溯保证枚举的不遗漏不重复2014-12-10 csdn博客 u010026901求两节点的最短通路，对于无权图，可以通过图的广度优先遍历求解。含权图一般通过Dijkstra算法求解。import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.M...

邻接矩阵（以顶点为中心），比较稀疏时，采用邻接表；图的两种遍历

2016年07月27日 36 阅读

邻接矩阵（以顶点为中心），比较稀疏时，采用邻接表；图的两种遍历2014-12-10 csdn博客 u010026901对于边比较稠密的图，可以采用邻接矩阵（以顶点为中心）的方式表示，而边比较稀疏时，采用邻接表的结构更合适。两种都不能直观表达哪两个点相连或者最短路径是什么。深度优先遍历类似于树的先根序遍历。与树不同的是，它需要对已经访问过的节点添加标记以免被重复遍历。public class Depth {/** * 对k号节点深度遍历 * @param a...

链表或字符串模拟加法、加一及乘法

2016年07月27日 38 阅读

链表或字符串模拟加法、加一及乘法2014-12-10 博客园 z陵链表模拟加法/字符串模拟二进制加法/数组模拟加一操作/打印1到最大的n位数/字符串模拟乘法============================================Add Two Numbers两个链表代表两个数字，每个结点的值都是一位数字，单链表逆序存放这两个数字，构造出一个新的链表，代表这两个链表的和。链表的尾插法，头结点dummy结点的运用，统一对prev指针的操作，/*...

并查集（Disjoint Set）

2016年07月27日 36 阅读

并查集（Disjoint Set）2014-12-10 cnblogs codingwu在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在规定的运行时间（1～3秒）内计算出...