图： PAT (Advanced Level) Practice 用到图的存储方式，但没有用到图的算法的题目 1122 Hamiltonian Cycle (25) 1126 Eulerian Path (25) 1134 Vertex Cover (25) 1142 Maximal Clique (25) 1154 Vertex Coloring (25) 图的遍历： 1.定义： 顶点的度：与该顶点相连的边的条数 顶点和边量化的属性分别为点权和边权 2.存储 邻接矩阵： 对称的矩阵 若题目中不存在权值，G[i][j]=1表示顶点i和顶点j之间有边，G...

#子查询 说明：当一个查询语句中又嵌套了另一个完整的select语句， 则被嵌套的select语句称为子查询或内查询 外面的select语句称为主查询或外查询。 分类： 按子查询出现的位置进行分类： 1、select后面 要求：子查询的结果为单行单列（标量子查询） 2、from后面 要求：子查询的结果可以为多行多列 3、where或having后面 要求：子查询的结果必须为单列 单行子查询 多行子查询 4、exists后面 要求：子查询结果必须为单列（相关子查询） 特点： 1、子查询放在条件中，要求必须放在条件的右侧 2、子查询一般放在小括号中 3、子查询的执行优...

#分页查询 应用场景：当页面上的数据，一页显示不全，则需要分页显示 分页查询的sql命令请求数据库服务器---->服务器响应查询到多条数据-->前台页面 语法： select 查询列表 from 表名 where 筛选条件 group by 分组 having 分组后 order by 排序列表 limit 起始条目索引，显示的条目数 执行顺序： 1、from子句 2、join子句 3、on子句 4、where子句 5、group by子句 6、having子句 7、select子句 8、order by子句 9、limit子句 ①起始条目索引从0开始，如果不写，则就是从0...

Dijkstra算法（迪杰斯特拉算法）用来解决单源最短路问题 如果边权出现负数，用SPFA 算法 可以用STL的优先队列priority_queue来优化 Dijkstra伪代码： //G为图，一般设为全局变量，数组d为源点到达各点的最短路径长度，s为起点 Dijkstra(G,d[],s){ 初始化; for(循环n次){ u=使d[u]最小的还未被访问的顶点的标号; 记u已被访问; for(从u出发能到达的所有顶点v){ if(v未被访问&&以u为中介点使s到顶点v的最短距离d[v]更优){ 优化d[v]; } } ...

法一：Dijkstra #include<iostream> #include<cstring> #include<algorithm> #define mm(a,x) memset(a,x,sizeof(a)) #define inf 0x3f3f3f3f const int maxn =510; using namespace std; int n,m,s,d; int map[maxn][maxn]; int dist[maxn]; int cost[maxn][maxn]; int dicost[maxn]; int path[maxn]; i...

记录第一标尺的pre[] pre[]不用初始化 每次找到最优的前驱时都会清空pre[v] 记录路径需要把中间点u录入后面 if(dist[u]+map[u][v]<dist[v]){ dist[v]=dist[u]+map[u][v]; pre[v].clear(); pre[v].push_back(u); }else if(dist[u]+map[u][v]==dist[v]){ pre[v].push_back(u); } DFS递归函数来解决第二标尺： 作为全局变量的第二标尺最优值opvalue 记录最优路径的数组path(使用v...

求任意两点u，v之间的最短路径长度，时间复杂度是O（n^3），顶点数在200以内，邻接矩阵实现（方便） Floyd算法描述： 枚举顶点k在1~n 以顶点k作为中介点，枚举所有顶点对i和j（i在1~n,j在1~n） 如果dis[i][k]+dis[k][j]<dis[i][j]成立 赋值 dis[i][k]+dis[k][j]=dis[i][j] Floyd的核心代码： void floyd(){ int i,j,k; for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=...

#DDL语言 说明：Data Define Language数据定义语言，用于对数据库和表的管理和操作 #----------------库的管理------------- #一、创建数据库 CREATE DATABASE stuDB; CREATE DATABASE IF NOT EXISTS stuDB; #二、删除数据库 DROP DATABASE stuDB; DROP DATABASE IF EXISTS stuDB; #----------------表的管理------------- #一、创建表 语法： CREATE TABLE [IF NOT EXISTS]表名(...

#一、修改表 语法：ALTER TABLE 表名 ADD|MODIFY|CHANGE|DROP COLUMN 字段名 字段类型 【字段约束】, #修改表名 ALTER TABLE stuinfo RENAME TO students; #添加字段 ALTER TABLE students ADD COLUMN borndate TIMESTAMP NOT NULL; DESC students; #修改字段名 ALTER TABLE students CHANGE COLUMN borndate birthday DATETIME NULL; #修改字段类型 ALTER TAB...

#DML DML(Data Manipulation Lauguage) 数据操纵语言: insert update delete 一、数据的插入 语法： 插入单行： insert into 表名（字段名1，字段名2，...） value(值1，值2，...) 插入多行： insert into 表名（字段名1，字段名2，...） values(值1，值2，...) 特点： ①字段和值列表一一对应 包含类型、约束等必须匹配 ②数值型的值，不用单引号 非数值的值，必须用单引号 ③字段顺序无要求 #案例1:要求字段和值列表一一对应，且遵循类型和约束的限制 INSERT INT...

#include<iostream> #include<cstring> #define maxn 1005 #define mm(a,x) memset(a,x,sizeof(a)) #define inf 0x3f3f3f3f using namespace std; int n,m; int map[maxn][maxn]; int dist[maxn]; int vis[maxn]; int prim(){ mm(dist,inf); dist[1]=0; int ans=0; for(int i=1;i<=n;i++){ ...

最小生成树定义： 在一个给定的无向图中，求一棵树使得这棵树拥有图中所有的顶点 所有边都是来自图中的边 满足整棵树的边权之和最小 最小生成树性质： ①最小生成树是树，因此其边数等于顶点数减一，且树内一定不会有环 ②对给定的图，其最小生成树可以不唯一，但其边权之和一定是唯一的 ③由于最小生成树是在无向图上生成的，因此其根结点可以是这棵书上的任意一个结点，题目中涉及到最小生成树本身的输出，为了使最小生成树唯一，一般都会直接给出根结点，题目中涉及到最小生成树边权输出，边权之和一样 prim算法 用来解决最小生成树问题 prim算法与DIjkstra算法思想几乎一致 ...

题目描述 著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。 内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。 输入格式： 输入首先在一行中给出正整数 N（< 1 0 5 10^5 1...

思路分析： 1.题目要求求解点权之和，这里区别一下点权和边权2.求最大的子链：就是树的直径 = ｍａｘ（最长链+次长链）3.因为有负权，所以不能使用BFS或DFS 参考代码： #include<bits/stdc++.h> using namespace std; const int N = 1e5+10, M = N * 2;／／双向边 const int inf = 0x3f3f3f3f; typedef long long ll; int n; int h[N],e[M],ne[M],idx; ll w[N]; ll ans = -inf;／／因为可能全部都是负数，所以答...