[综合] Dijkstra算法---模板

Dijkstra算法：单源最短路径 给定一个带权有向图G=(V,E)，其中每条边的权是一个非负实数。另外，还给定V中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 下面给出两个计算单源最短路径的模板。 ①邻接矩阵...

[综合] POJ 3680(费用流)

题意: 见《挑战》P246. 直接套用模板即可： //标号法，设立一个标号数组h[MAXN] #include<iostream> #include<cstring> #include<algorithm> #include<deque> #incl...

[综合] POJ 3984---迷宫问题(BFS，迷宫最短路径且输出路径)

原题： BFS入门题，打印路径记录前驱就可以了。然后可以递归打印，也可以非递归打印路径： 递归打印路径： #include<iostream> #include<cstdio> #include<algorithm> #include<queue> ...

[综合] 二叉树遍历的应用（递归!递归！递归！）

在学习《数据结构》中二叉树这块的时候，能很好地帮助我们学习递归思想， 本文就二叉树的遍历的递归思想，写点二叉树的常见性质题（什么高度，同构，叶子节点各种乱七八糟~ps：其实我只是想备考下期末考！） 二叉树定义： typedefcharElemType; typedefstructBiNode {...

[综合] 06-图2 Saving James Bond - Easy Version（25 分）---DFS

06-图2SavingJamesBond-EasyVersion（25分） Thistimeletusconsiderthesituationinthemovie"LiveandLetDie"inwhichJamesBond,theworld'smostfamousspy,wascapture...

[综合] 07-图5 Saving James Bond - Hard Version（30 分）BFS记录路径

07-图5SavingJamesBond-HardVersion（30分） Thistimeletusconsiderthesituationinthemovie"LiveandLetDie"inwhichJamesBond,theworld'smostfamousspy,wascapture...

[综合] 二叉搜索树（BST，基本操作实现）

二叉搜索树（BinarySearchTree)也叫做二叉排序树或者二叉查找树。 相比正常的二叉树就是多了一条性质：左子树的键值小于其根节点的键值，右子树反之，左右子树都是二叉搜索树。 主要操作函数：（还是递归递归递归！！！）PositionFind(ElementTypeX,BinTreeBST)...

[综合] 校oj10532: 生成字符串（dp，最优状态转移）

题目： 10532:生成字符串TimeLimit:1SecMemoryLimit:128MB Submit:91Solved:5 [Submit][Status][WebBoard] Description Flowersea想为某些编程竞赛生成一个输入文件。 他的输入是由n个字母“a”组成...

[综合] 优先队列---二叉堆

优先队列---二叉堆： 二叉堆是一棵完全二叉树，最大堆（最小堆）中，所有根节点的键值都要比对应的子树要大（小）。 由于是完全二叉树，所以存储结构可以采用数组。 最大堆的创建： #include<iostream> #include<cstdio> #include<a...

[综合] POJ1521---哈夫曼编码，求最优WPL

POJ1521---哈夫曼编码 题目描述 输入一个字符串，长度不超过100，仅由大写字母和下划分组成。求用最好的字符编码方式，令总长度最小。 输入 多组数据，每组数据在一行上输入一个字符串，格式如前所述 当遇到END时，表示输入结束 输出 对应每个输入，在一行上输出3个信息：首先是每个字母按固定长...

[综合] 数据结构---排序算法(比较排序)

目录 插入排序 冒泡排序 希尔排序 选择排序 堆排序 归并排序 快速排序 插入排序 voidInser_Sort(intA[],intN) {inti,p;for(p=1;p<N;p++){inttmp=A[p];//从第二个元素开始插，出队。for(i=p;i>0&&...

[综合] HDU---1427（24点游戏，DFS回溯）

题意： 速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人...

[综合] 以 lower_bound 函数入门二分搜索（形成自己的代码风格）

Lower_bound函数： 给定长度为n的单调不下降数列a0,a1,,,an-1，和一个数k，求满足ai>=k条件的最小的i，不存在的情况下输出n； 每个人都会，但是一定要从这种简单题中，形成自己的二分搜索的编程风格！对后面的难度较大、复杂的二分搜索大有裨益！ 这里给出我的代码和理解： ...

[综合] POJ---1064（Cable master，简单二分判断可行性）

题意： 有N条绳子，他们的长度分别为Li，如果从他们中切割出K条长度相同的绳子的话，这K条绳子每条能最长能多长？答案保留小数点后两位。 题解： 判断可行性，很明显的二分搜索。寻找最大的L，满足能切割出K条绳子！ 题目虽然简单，但是体现了二分搜索的基本思想和编程风格（这里是浮点数，所以怎么循环还是要...

[综合] POJ---2456（Aggressive cows，贪心最大化最小值）

题意： 有N头牛，其中有M头倔牛，要求最大化这M头牛最小距离。 题解： 最大化最小值，二分！对于所有的距离贪心判断这M头牛是否能放下去。 个人认为本题数据有问题，对于M=2的时候，好像~~~没有判定！ 因为代码中初始化ub为x[N-1]-x[0]或者x[N-1]-x[0]+1都能AC。显然前者是...

[综合] POJ---3258（River Hopscotch，最大化最小值）

题意： 和上一道题类似，只不过把倔牛换成了石头，求n-m个石头的最大的最小距离。 最大化最小值。 题解： 最大化最小值，二分！和上一道题几乎一样，这里只不过多了，最后一个固定的石头！要判定下放下去的n-m个石头，最后一个放下的石头离固定石头的距离是否>=d; #include<cs...

[综合] POJ---3273（二分，最小化最大值）

和这道题一样了： Description 聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板） 聪哥不喜欢身上一次性有太多的钱，于是他想...

[综合] POJ3104（Drying，最小化，可行解）

题意： 蒸衣服，单位时间掉K单位的水。不蒸单位时间掉1单位的水。给定n件衣服的水量和K，求K的最小值。 题解： 最小化可行解。 #include<cstdio> #include<iostream> #include<algorithm> #include<...

[综合] POJ---3111（二分，最大化平均值）

题意： 最大化平均值的模型： 有N个物品的重量和价值分别为Wi和Vi，从中选取K个物品使得单位重量的价值最大。也就是使得K个物品的ΣVi/ΣWi最大。 使用二分搜索解决这类问题： ΣVi/ΣWi>=x也就是Σ(Vi-x*Wi)>=0 去找最大的可行解x即可！X越大，式子左边越小，一直逼到...

[综合] POJ---3579（Median，二分搜索）

题意： 给定N（3≤N≤1,00,000）个数，两两的差值，形成一个新序列，求这个新序列的中位数。 题解： 直接的是算出来两两的差值，然后再排序。这样以来时间复杂度来到了O（N2）,肯定会超时。 二分思想：每次判断Mid是否符合中位数：扫描一遍所有的数，计算每个数能与多少数构成差值小于Mid，将所...