dj 访问新点记得打标记 #include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 1145140; struct node { int to,w,nxt; }edge[N]; int he…

1．微型计算机中，控制器的基本功能是（ ）。 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 获取外部信息 D. 存放程序和数据 在下列关于图灵奖的说法中，不正确的是（ ）。 A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止，还没有…

树形dp 模板题 没有上司的舞会 (1) 初始化：题目说领导和员工的关系是树形结构，为了方便用邻接矩阵E存储每个人的员工，E是一个二维数组，在E[i]行中存储了所有i的直接员工。题目在输入的时候是先输员工在输领导，所以要注意反过来。并且题目没有指定老板一定是谁，所以需要找到老板，具体的方法是，依次遍历每个人的直接员工，若有一个人从没有出现在别人的员…

状态压缩 模板题 数字游戏 状态压缩：对每一行状态进行压缩，用1表示选择，0表示不选择，并把他看成二进制数，如010010就表示选择第2个、第5个数，一行有至多6个数，也就是一个六位的二进制数，假设0也表示一种状态，则最大2 ^ 6 - 1种，转化为十进制数最大才63。 预处理：并非每一种方案都可以选择，题目要求不能相邻，即011000就是一种不正…

后缀数组 有一个字符串 s = ababba. 将他的后缀按字典序排序. a ababba abba ba babba bba 这个数组就是后缀数组,使用string存储,空间复杂度O(n^2). 用一个数来记录后缀在原数组中的起始位置,存在一个数组p中,p[i]表示字典序第i位的是在原数组中第p[i]个位置起始的. 空间复杂度O(n). 那么如何…

最小生成树 最小生成树就是将一张图去掉几条边后所形成的树边权之和最小. Kruskal 在不形成环的前提下,优先选择边权最小的边组成树,直到所有点都连通. 使用并查集检查联通后两个顶点是否会形成环. 首先对所有边按边权排序. 每次拿出一个边,若和现有不存在同一个集合中,则添加这条边. 添加n-1次,就完成了最小生成树. #include <i…

关键路径 假设有一个工作,该工作分成若干个工序,每个工序都有自己的时间,且必须在前序活动完成后才能进行,若有一些工序必须按时完成,就称之为关键活动,由起点出发全由关键活动组成的最长路径就叫做关键路径. 要求关键路径,我们需要知道两件东西,第一件是该活动最早的开始时间,第二件是该活动最晚的开始时间. 若最早开始时间减去最晚开始时间为0,则该活动必须准…

拓扑排序 拓扑排序,就是经过图中某个点时,必须要经过他的前置节点. 一张图可以有好几条拓扑排序. 图中的图 5 ——> 11 ——> 9 就是其中之一条拓扑排序. 拓扑排序 使用bfs的方式来找到拓扑排序. 首先先统计一下每个点的入度,入度为0的就是起点.因为他没有任何前置节点. 将起点入队. 从起点出发,遍历所有连接的点,然后删除这条…

区间dp 区间dp就是枚举一个起点,一个中转点,一个终点,以此来求解最短路. 主要适用于不满足三角形不等式,也就是绕路比直线近的清空 Floyd Floyd主要用于解决图论最短路. 他使用的是区间dp思想. 先枚举中转点 再起点 最后终点. 枚举的顺序不能变换,因为我们是要固定一个中转点,通过起点走过中转点再到终点. 初始化 dp[i][j] 表示…

背包dp 01背包 01背包是指,有n件物品,每件物品有自己的重量W和C且不可分割,只能选择一次,背包容量有限,求要怎么样拿物品才能使得价值最大. 贪心显然无法解决此问题,因为物品无法进行分割.当有物品重量很大,价值最大,有物品重量最小,价值次大时,按照贪心策略就会出现问题. 01背包 1.初始化一个数组f[i][j],表示当物品数量为i时,背包容…