夏令营7.24总结

今天去报告厅上大班课，热死了，上了一个上午。

图论建图

基本规律

图中的点代表了状态，边代表转移方式、约束等状态之间的关联，然后利用一些基本的图论算法解决问题。

图论算法

最短路算法

• Floyd算法：全源最短路，$O(n^3)$

  Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

• Dijkstra算法：单源最短路，$O(n^2)/O(m\ \log\ n)$

  该算法采用贪心策略，通过不断扩展已知最短路径区域（集合$S$）来逼近目标。初始化时，将起始点加入$S$，并设置其最短距离为0。随后，从待处理节点中选取当前距离起始点最近的节点$u$，将其加入$S$，并更新其邻接节点的最短距离（若通过$u$的路径比原距离更短）。重复此过程直至所有节点被纳入$S$。

• SPFA：容易被卡，不建议使用。

  SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford算法 的队列优化版本，主要用于求解含负权边的单源最短路径问题，并可检测图中是否存在负权环。该算法在图中出现负环时可能会陷入死循环。非负权图种则更建议使用Dijkstra算法。

拓扑排序

对于一幅有向无环图，可以对其节点进行拓扑排序，使得所有的有向边$u\rightarrow v$满足$u$排在$v$前面。

方法：维护一个队列，里面包含所有当前的零入度点，每次取出一个并删除，再将其所有相邻的点的入度设为$-1$，如果减成了0那么就加入队列。不断操作直到队列为空。

复杂度：$O(n+m)$

例题：P4316

最小生成树

• Kruskal：较常用，$O(m\ \log\ m)$，如果不连通则得到最小生成森林。

  克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，Kruskal较适合于求边稀疏的网的最小生成树。

• Prim：不常用，$O(n^2)/O((n+m)\ \log\ m)$（堆优化）

  该算法使用贪心策略，每次选择连接已选顶点集（$U$）与未选顶点集（$V-U$）的最小权值边，确保局部最优解最终导向全局最优。‌‌

• Boruvka：对于特定的题目有奇效，$O(m\ \log\ n)$例题CF888G

  ‌初始化‌：将每个节点视为一个独立的连通块，共 n 个连通块。

  合并过程：

  • 对每个连通块，计算其与外部连通块的最短边（若边权相同则选择编号较小的边）。
  • 合并选中的连通块，重复此过程直至所有节点连通。

连通性算法

• Tarjan1：有向图强连通分量，无向图边双连通分量，$O(n+m)$。常碰到将一个连通分量缩点，在拓扑排序的套路。
• Tarjan2：无向图点双连通分量，$O(n+m)$。常见于仙人掌图，有时配合圆方树操作。
• 例题：P2341，P3627

例题

P5960 差分约束

将一个$x_i-x_j\le y$的限制，看成一条从$x_i$到$y_i$的权值为$y$的有向边。

可以发现，若$y$均为整数，则从任意点出发得到的每个点的最短路长度即可满足要求。

若$y$可为负数，则需考虑有无负环。

P4568

给定一个带边权的无向连通图，有$n$个点和$m$条边，无自环与重边。

假设一条路径经过的边权依次为$w_{1…k}$，则这条路径的权值为$\sum_iw_i-\max_i+\min_iw_i$。

找出点1到其他每个点的最小权值路径。

$n,m\le2\times10^5$

结尾

今天的算法比较难，所以写的比较少，但是其实理解的量还是比较大的。