1.图上bfs 例题求距离 给你一张n个点m条边的无向简单图，点的编号为1到n，每条边的长度都是1现在有k组询问，每组询问我们想知道两个点u,v的距离。 输入格式 第一行三个整数n,m,k分别表示图的点数、边数和询问数。接下来m行，每行两个整数x,y，表示x号点和𝑦号点之间有一条边。接下来k行，每行两个整数u,v表示一组询问。 输出格式 输出共k行，对于每一组询问，输出一行一个数表示两个点的距离，如果两个点不连通，输出-1。 样例输入 32212231213 样例输出 12数据规模 对于所有数据，保证2≤n≤20000,0≤m≤100000,1≤k≤10,1≤x,y,u,v≤n,x≠y ...

bellman-ford算法的思想： 若有向图有n个点，m条边。扫描所有边，对每条边进行一次松弛（即对a,b为端点，权重为w的边，dist[b]=min(dist[a],dist[a]+w））重复此流程（最多重复n次）直到没有更新操作发生 例题1bellmanford板子 给你一张n个顶点m条边的有向简单图，顶点编号从1到n，每条边都有一个边权，边权为非负整数。 现在有k组询问，每组询问读入两个整数x,y请求出从x号点到y号点的最短路的长度。如果不存在从x号点到y号点的路径，请输出-1。 输入格式 第一行三个整数n,m,k表示图的顶点数、边数和询问次数。 接下来m𝑚行，每行三个整数x,y,...

生成树:如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树 最小生成树:边权和最小的生成树叫做最小生成树。如果原图不连通，则没有最小生成树 求最小生成树有两种方法：prim和kurskal 一.prim算法 将最小生成树看做一个集合，每次选取距离集合最近的点，如果这个点不在集合中则加入集合，也就意味着这个点和集合里的点所连成的边加入了集合。最后等到所有点都加入集合则所有进入集合的边构成最小生成树。 例题1prim板子 给你一张n个顶点m条边的无向简单连通图，顶点编号从1到n，每条边都有一个边权，边权为非负整数。 请求出这张图的最小生成树，只需要输出最小生成树的边权和即...

定义:对一个有向图构造拓扑序列，排序类似流程图那样按先干什么后干什么这样排序拿大学教学安排举个例子（图来自oiwiki） 先不要考虑操作系统到数据结构那条蓝线。 那么我们要先学程序设计才能学习后面的算法语言，离散数学等等。那么在拓扑序列中，程序设计就要在算法语言，离散数学这些前面。 但拓扑序列并不是唯一的，比如高等数学和程序设计是互不影响的，那么在拓扑序列中高等数学和程序设计谁在前谁在后都可以 现在让我们考虑操作系统到数据结构那条蓝线。 现在操作系统和数据结构都互为各自的前置知识，这样就会出现矛盾，不知道拓扑序列中究竟该谁在前谁在后。 我们可以发现:一个图中所有点是否可以构成拓扑序列可以作...

一.定义 二分图是节点由两个集合组成，且两个集合内部没有边的图。 换言之，存在一种方案，将节点划分成满足以上性质的两个集合。 比如下图就是一个二分图，两个集合的元素可以用两种颜色表示，每条边上连接的点属于不同的集合，相同集合的两个点上没有边 注意：二分图中不存在元素为奇数的环 二.二分图的判定（染色法） 我们可以枚举每个点，如果点还没被染色，那么将其染为1并用dfs遍历这个点所在的连通块的每个点，染1染2这样交替进行，一旦发现冲突（两个相邻的点是同一个颜色）那么该图就不是一个二分图 例题二分图判定板子 给你一张简单无向图，你需要判断这张图是否为二分图。 图用以下形式给出： 第一行输入...

分治的核心思想是 自上而下通过递归不断将大问题拆分成两个或多个子问题，直至被拆分出来的子问题可以通过一些简单的方法解决 然后再自下而上地用子问题的解求解大问题的解 最终我们能得到初始问题的解 解决分治问题的时候的代码基本就是 限制左边界右边界的时候返回值 将区间一分为二，根据条件进行模拟 例题1求逆序对 有n个数a1,a2,…,an，对于其中的两个数字x,y，如果满足x出现的位置在y出现的位置前面并且x比y大，则称(x,y)为数组a的一个逆序对。请问数组a的逆序对一共有多少个？形式化的说，请求出有多少组(i,j)满足i<j并且ai>aj。 输入格式第一行一个整数n。 ...

一些定义 先序，中序，后序遍历中的序是遍历根的顺序 层序遍历就是这个数的bfs序列 树的存储 有很多种存储方式，一般用结构体数组。数组下标对应这个数的结点，既可以存左儿子右兄弟又可以存左儿子右儿子。下面来看一些题真切的感受一下代码 例题1遍历完全二叉树 http://oj.daimayuan.top/course/7/problem/430 题目 给你一棵n个节点的完全二叉树，节点的编号为1到n，二叉树的根为1号节点。编号为i(1≤i≤n)的节点的左儿子如果存在的话，编号为i+i；编号为i(1≤i≤n)的节点的右儿子如果存在的话，编号为i+i+1。 现在请你求出这棵完全二叉树的先序、...

引入 有n个物品和一个容量为W的背包，每个物品有重量w{i}和价值v{i}两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。我们之后涉及到的所有背包问题都会根据这个背景展开 1.01背包 每个物品只能选取一次。这样每个物品都会只有两种状态：选与不选。用二进制表示就是0与1也就是01背包 例题 有n种物品要放到一个袋子里，袋子的总容量为m，第i种物品的体积为vi，把它放进袋子里会获得wi的收益，每种物品至多能用一次，问如何选择物品，使得在物品的总体积不超过m的情况下，获得最大的收益？请求出最大收益。 输入格式第一行两个整数n,m。 接下来n行，...

定义 具有单调性的栈结构，该数据结构的目的是快速找到与一个元素距离最近的元素 过程（摘自oiwiki） 插入将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。 例如，栈中自顶向下的元素为{0,11,45,81}。 插入元素14时为了保证单调性需要依次弹出元素0,11，操作后栈变为{14,45,81}。 每个元素都只入栈一次，出栈一次，时间复杂度是o(n) 接下来看一些例题了解一下具体写完与应用 例题1求下一个最大的数（单调栈例题） 给你n个整数a1,a2,…,an，请问从每个数字往后看，第一个比它大的数字的下标是...