Z_L_G

分类

总结(19) 训练赛(6) 题解(96)

/ 注册

全部文章（共119篇）

图论-一些建图

多起点多终点问题设置一个超级起点和超级终点，然后正常做多层次问题不同的问题有不同的设计方法，最重要的是不要出现只之前不存在的边每一层内设置一个平台点，去平台点花费，出平台点不花费，平台之间代价为0 设计两个点，一个点接受下一层点的进入，并指向上一层点，经过的代价为t，另一个点接受上一...

图论

2025-07-13

0 6

算法入门-Ranking the Cows

题意 n个数，确定了m对关系(a>b) 求还需要多少对关系就能确定任意两个数之间的大小思路把大小关系视为一条有向边这个题就变成了任意两个点是否联通考虑使用FLoyd，但是n是1000量级的，刚好爆炸使用bitset优化足够 floyd算法可以传递闭包关系 bitset错误赋...

位运算优化 floyd传递闭包

2025-07-13

0 7

算法入门-HDUOJ5521Meeting

题意 n个点，m个集合，在i-th集合内相互移动的代价为t-th 两个人从1和n开始移动，求碰面最短时间和碰面的点思路强行给每个集合之间的点互相连边复杂度会到不可以对于这种集合/平台类的问题，我们通常选择给每个集合/平台单开一个点，集合中所有点到这个单开点建双向边，过去的代价为t，回...

妙妙题裂点最短路

2025-07-13

0 7

算法入门-[SCOI2012]滑雪与时间胶囊

题意给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点特别的，两个点一样高，就认为是双向边求出最多能到达的点的个数，以及到达这些点需要的最小距离思路先dfs一遍，确定哪些点能到类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两...

最小生成树深度优先搜索

2025-07-13

0 7

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

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

拓扑排序反向建边

2025-07-11

0 8

算法入门-胖胖的牛牛

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

广度优先搜索

2025-07-11

0 11

图论-最短路

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

2025-07-11

0 10

图论-最小生成树

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

图论

2025-07-11

0 8

图论-AOE与关键路径

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

图论

2025-07-11

0 9

图论-AOV与拓扑排序

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

图论

2025-07-11

0 8