Z_L_G

分类

总结(20) 训练赛(18) 题解(129)

/ 注册

全部文章（共165篇）

算法入门-[HNOI2015]菜肴制作

#反向建边 #拓扑排序题意有n个菜，m个条件约束条件(a,b)，表a必须在b之前除了约束条件外，要保证序号小的的尽可能先做在满足所有限制的前提下，1 号菜肴”尽量“优先制作；在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；以此类推。例：共4 道菜肴，两条限...

拓扑排序反向建边

2025-07-11

0 33

算法入门-胖胖的牛牛

题意 n*n的正方形地图，从起点走到终点，图中有一些障碍物不能走求最小转弯次数思路图不大，迷宫问题，考虑搜索，不再记录步长，而是在走每一步的时候考虑和走过来的方向是否相同，如果不同就给转弯次数+1 用一个优先队列避免重复走不开vis，否则部分优势可能掩盖全局劣势也可以最短路做，每个点...

广度优先搜索

2025-07-11

0 40

图论-最短路

特殊最短路树：直接起点dfs搜索到终点即可有向无环图：拓扑排序，删掉每一个点时更新后继的最短距离边权全部为相等：bfs 单源最短路从一个点出发到其它顶点的最短路径长度基本操作：松弛这样的(u,v)称为紧的，可以对它进行松弛 dijkstra 不能存在负边，每个边会被访问一次，...

2025-07-11

0 48

图论-最小生成树

Prim 从单一顶点开始不断加入最小的边，且边的一个顶点在树中一个顶点不在 #include<bits/stdc++.h> using namespace std; typedef struct{ int t,l,nxt; }E; E edge[1010110]; in...

图论

2025-07-11

0 34

图论-AOE与关键路径

关键路径 AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应，它通常表示一个工程的计划或进度。 AOE网是一个带权的有向无环图，图中的：边：表示活动(子工程)，边上的权：表示该活动的持续时间，即完成该活动所需要的时间；顶点：表示事件，每个事件...

图论

2025-07-11

0 55

图论-AOV与拓扑排序

引入一个工程有许多子工程，称为活动，在有向图中用顶点表示活动，有向边表示活动的先后顺序，这样的图称为AOV网，在AOV网中为了更好的完成工程，需要满序先后关系，将各活动排一个先后次序，就称为拓扑排序问题对一个AOV图，判断能否排序，并进行排序解决方法从有向图中选一个没有前驱的结点...

图论

2025-07-11

0 35

图论-图存储总结

1.邻接矩阵二维数组，如果有重边就按题意考虑是否可以合并成一条边，或者只取一条边 2.邻接表链表结构，头插法 3.vector 开一个vector数组来简化邻接表，但有时不够块 4.链式前向星开一个结构体存边信息，开一个数组存每一条边，开一个head记录连接着这个点的下一个点是谁...

图论

2025-07-11

0 32

图论-欧拉图判断

什么是欧拉图图G中存在一个路径，包含每个边恰好一次，该路径是欧拉路径如果一个回路是欧拉路径，就称为欧拉回路有欧拉回路的图是欧拉图，有欧拉路径没有欧拉回路的图称为半欧拉图怎么判图联通无向图所有顶点的度是偶数有向图所有顶点的入度等于出度

图论

2025-07-11

0 30

算法入门-[NOIP2003]加分二叉树

题意一个1-base二叉树，n个结点，中序遍历为(1,2,3,...,n),每个点有一个val，选择一个子树的加分规则如下：如果某个子树为空，就视为val=1，叶子节点分数为本身的分数求符合中序遍历的加分最高的二叉树，输出加分和前序遍历思路对于一段中序遍历序号，总需要选择一个根，切分...

区间dp dp

2025-07-09

0 35

算法入门-树学

题意一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和求选择哪个点为根时可以使深度和最小思路让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和但是让每一个点跑一遍复杂度会爆炸能不能只跑一遍？如果只跑一遍，根变换怎么办对于一个选定根的树，如果...

深度优先搜索 dp

2025-07-09

0 22