『算法-ACM竞赛-图论』LCA-树上倍增法（在线）
『算法-ACM 竞赛-图论』LCA-树上倍增法（在线）图论–LCA–树上倍增法（在线）/* * LCA在线算法(倍增法) */ const int MAXN = 10010; const int DEG = 20; struct Edge { int to, next; } edge[MAXN * 2]; int head[MAXN], tot; void ad
『算法-ACM竞赛-图论』LCA-在线RMQST
『算法-ACM 竞赛-图论』LCA-在线 RMQST图论–LCA–在线 RMQ ST板子测试 POJ1330，一发入魂，作者是 KuangBin 神犇，感谢? #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10010
『算法-ACM竞赛-图论』LCA-Tarjan（离线）
『算法-ACM 竞赛-图论』LCA-Tarjan（离线）图论–LCA–Tarjan（离线）* * 给出一颗有向树，Q个查询 * 输出查询结果中每个点出现次数 * 复杂度O(n + Q); */ const int MAXN = 1010; const int MAXQ = 500010; // 查询数的最大值 // 并查集部分 int F[MAXN];
『算法-ACM竞赛-图论』Floyd总结
『算法-ACM 竞赛-图论』Floyd 总结图论–Floyd 总结Key word:① 最短路② 传递闭包:大小关系 数值关系 先后关系 联通关系③floyd 变形④ 实现方式:插点发法⑤ 思想:动态规划 1.最短路:最短路是 floyd 的一个基本应用，但是对于不是裸题的最短路该怎么使用是我们要关注的，其次什么时候使用也是要注意的，至于什么时候使用 Floyd，首先先看数据量，三重循环始终是 F
『算法-ACM竞赛-图论』Dijkstra算法总结
『算法-ACM 竞赛-图论』Dijkstra 算法总结图论–Dijkstra 算法总结Key word： ①BFS 转换 Dijkstra ② 其他关系转化为最短路 ③ 反向建边及反向 Dijkstra ④ 稠密图、稀疏图 ⑤ 链式前向星 ⑥Vector 建图 ⑦ 超级源点&汇点 详解： 1.BFS 转换 Dijkstra： 对于一些路径的的问题及一些特殊的搜索题目，如果数据量很多但是处理
『算法-ACM竞赛-图论』DFS总结
『算法-ACM 竞赛-图论』DFS 总结图论–DFS 总结1.Key word：① 双向 DFS ② 回溯 今天就看到了这么多 DFS，其实 DFS 更倾向于枚举所有情况。 对于双向 DFS，我们考虑看看最短路，起点做一下搜索，记录一下到所有点的距离，终点做一下搜索，记录一下到所有点的距离，那么起点到任一点的距离加上终点到任一点的距离那不就是起点到终点经过这一点的最短距离，我觉得 BFS 也可以实
『算法-ACM竞赛-图论』BFS总结
『算法-ACM 竞赛-图论』BFS 总结图论–BFS 总结1.关于 BFS 的 Key_word： ①hash 或状态压缩记录状态 ② 状态剪枝 ③ 反向 BFS ④ 双向 BFS ⑤ 特殊初始化 VIS 数组 ⑥ 动态图的搜索 ⑦ 优先队列优化搜索 ⑧ 数位搜索 下面是一一讲解： 1.hash 或状态压缩记录状态 ： 当状态太多而且边界也广时数组难以存储状态时或者题目对空间的要求较为苛刻，这时候
『算法-ACM竞赛-图论』2-SAT-详解
『算法-ACM 竞赛-图论』2-SAT-详解图论–2-SAT–详解问题描述：现有一个由 N 个布尔值组成的序列 A，给出一些限制关系，比如 A[x]AND A[y]=0、A[x] OR A[y] OR A[z]=1 等，要确定 A[0..N-1]的值，使得其满足所有限制关系。这个称为 SAT 问题，特别的，若每种限制关系中最多只对两个元素进行限制，则称为 2-SAT 问题。 由