图算法大全：网络流、最小生成树、最短路径与更多

"ACM_er专用模板" 本文档是针对ACM（国际大学生程序设计竞赛）参赛者的一份算法模板集合，涵盖了多种常用的图论和数据结构算法，旨在帮助参赛者快速解决各类竞赛题目。以下是这些算法的详细说明： 1. **Tarjan算法**：一种用于查找图中强连通分量的深度优先搜索算法。它通过维护一个栈来跟踪当前路径，并计算每个节点的低点和发现时间，从而找出所有强连通分量。 2. **网络流算法**： - **EK算法**（Edmonds-Karp算法）：是增广路径算法的一种，用于求解网络的最大流问题。它利用了Bellman-Ford算法的思想，每次选择增广路径中最短的一条，确保找到的是最大流量。 - **ISAP算法**（Improved Simplex Algorithm for Paths）：是求解线性规划问题在网络流框架下的实现，适用于解决最小费用最大流问题。 3. **最小生成树算法**： - **Kruskal算法**：按照边的权重从小到大选择边，但避免形成环路，直至连接所有节点，得到的树即为最小生成树。 - **Prim算法**：从一个节点开始，逐步添加边，每次添加一条使得当前树与未加入树中的节点之间边的权重最小的边，直至包含所有节点。 4. **最短路径算法**： - **Dijkstra算法**：用于寻找图中两点间最短路径，采用贪心策略，每次扩展距离源点最近的节点。 - **Floyd算法**（Floyd-Warshall算法）：用于求解所有节点对之间的最短路径，通过动态规划的方式，逐步考虑所有中间节点。 - **SPFA算法**（Shortest Path Faster Algorithm）：基于队列的最短路径算法，处理负权边时可能比Dijkstra更有效。 - **Floyd-Ford算法**：可能指的是Ford-Fulkerson算法，用于求解网络最大流问题。 5. **RMQ问题**（Range Minimum Query）：在数组中查找给定区间内的最小值，常用于动态查询优化。 6. **Trie字典树**：一种字符串查找数据结构，通过树形结构高效地存储和检索前缀相同的字符串。 7. **拓扑排序**：对于有向无环图（DAG），将其节点排序，使得对于每一条有向边 (u, v)，节点u总是在节点v之前。 8. **Pick定理**：用于计算简单多边形内格点数的几何定理，可应用于面积计算。 9. **匹配算法**： - **匈牙利算法**：解决二分图中的完美匹配问题，如Kuhn-Munkres算法，可以找到最大匹配。 - **最大权匹配**：在图中寻找边权最大的匹配，可以用于资源分配等实际问题。 10. **树状数组**（也称作二叉索引树或 Fenwick Tree）：一种数据结构，用于高效地进行区间更新和单点查询操作，常用于求解前缀和等问题。 这些算法是ACM竞赛中常见的工具，掌握它们能够提升解题效率，应对各种复杂问题。