Z_L_G

总结

训练赛(6) 题解(96)

/ 注册

全部文章 / 总结（共17篇）

图论-一些建图

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

图论

2025-07-13

0 10

图论-最短路

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

2025-07-11

0 15

图论-最小生成树

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

图论

2025-07-11

0 12

图论-AOE与关键路径

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

图论

2025-07-11

0 12

图论-AOV与拓扑排序

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

图论

2025-07-11

0 12

图论-图存储总结

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

图论

2025-07-11

0 12

图论-欧拉图判断

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

图论

2025-07-11

0 11

最大全0子矩形问题

题意对于一个由0,1构成的矩形，求解其中面积最大的全0子矩形，和全0子正方形思路法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立复杂度：法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形复杂度：,(m为1的个数，最多到) 法三：悬线法，...

dp

2025-07-06

0 17

状压dp

什么是状压对于题目中一种复杂的状态，如多维，多行，多条路，某种方案，某种集合等压缩成一个整数的过程就是状态压缩这也可以看作是一个Hash的过程除去压缩状态的过程，其实它整体和普通的dp差别不大，都是从已知过程推向位置过程压缩的意义在于把一个一般无法描述的状态，变成一个包含多种信息的状态，而...

状压dp

2025-07-06

0 17

TSP问题

题意旅行商问题，在一个若干点的图中，设计一条最短路径，途径所有点有时最终会要求回到原点思路状压dp 访问每一个点的时候需要考虑当前已经访问了哪些点走到某一个点的最短路径应该是所有(上一步最短路径+上一步所在点到当前点距离)取最小表示当前状态为st，最后一个点时i的最短路径代码...

状压dp

2025-07-03

0 21