POJ2352 #include<iostream> #include<cmath> #include<cstdio> #include<sstream> #include<cstdlib> #include<string> #include<cstring> #i…
POJ2352（树状数组）
树状数组
版权声明：“树状数组简介”中所用插图出自这里。链接到的是转载博文，转载作者未链接原文。侵删。其余讲解部分为本人原创。 1.例题（HDU1166） 题意：给出一个序列，有如下操作：为其某子区间中的所有数价钱相同值，查询其某子区间内所有值的和。要求在查询操作后输出所求的和。 2.分析引入 乍看之下，这道题直接用for循环在指定区间内逐个求和。然而，必须…
ACM暑假学习与复习笔记
知识点 树状数组 题目/比赛 HDU1166（树状数组）
《数据结构》期末提纲之拓扑排序
1.拓扑排序简介 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个…
《数据结构》期末提纲之最短路
1.例题 本文以HDU2544为例： 题目大意 给出一个带权无向图，求其从起点到终点的最短路径。 2.Dijkstra算法 算法思路 Dijkstra算法算一种贪心算法，通过不断选择中间点找出起点到各个点的最短路（这个操作被称为松弛）。该算法常用于求单源图的最短路，具体见伪代码。 伪代码 Dijkstra(){ 取邻接表起点行作为最短路记录数组； …
《数据结构》期末提纲之最小生成树
版权声明：本文前两个图片出自这里，图片所属博主允许转载。本文其他部分若未说明即为原创。 1.最小生成树简介 在一给定的无向图G=(V,E)中，(u,v)代表连接顶点u与顶点v的边，而w(u,v)代表此边的权重，若存在T为E的子集且为无循环图，使得图中路径权值和最小，则此T为G的最小生成树。 2.Prim算法 Prim算法相当于将点一个一个增加，算法…
《数据结构》期末提纲之DFS与BFS
1.广度优先搜索（BFS） 简介 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，…