ACM/ICPC算法模板：吉林大学计算机科学与技术学院

"ACM算法模板(吉林大学)" 是一份由吉林大学计算机科学与技术学院2005级学生在2007-2008学年整理的算法参考资料，包含了丰富的图论、网络流和数据结构相关知识点，旨在为ACM/ICPC竞赛提供代码模板和学习指导。 一、图论算法： 1. **DAG的深度优先搜索标记**：用于遍历无向图或有向无环图(DAG)，识别图的结构。 2. **无向图找桥**：找出图中的桥（断点），桥连接了两个原本不连通的部分。 3. **无向图连通度(割)**：计算图的连通分支数量，以及最小割。 4. **最大团问题**：寻找图中最大的完全子图，每个节点都与其他所有节点相连。 5. **欧拉路径**：寻找通过图中所有边一次且仅一次的路径。 6. **DIJKSTRA算法**：求解单源最短路径问题，有两种实现方式：数组实现和优化后的O(E*LOGE)版本。 7. **BELLMAN-FORD算法**：处理有负权边的情况，寻找单源最短路径。 8. **SPFA算法**：一种快速但可能有负循环的最短路径算法。 9. **第K短路**：除了最短路径外，寻找第K短的路径，可以使用DIJKSTRA或A*算法实现。 10. **PRIM算法**：求解最小生成树，用于加权无向图。 11. **次小生成树**：寻找加权无向图的第二小生成树。 12. **最小生成森林问题**：解决多棵树的最小生成树问题，使用kruskal或prim算法。 13. **有向图最小树形图**：找到有向图的最小树形图，即最小的树形子图，使得原图中的每条边都能在树形子图中通过一条路径表示。 14. **TARJAN强连通分量**：识别有向图中的强连通分量，即互相可达的节点集合。 15. **弦图判断与完美消除点排列**：在树状图上进行操作，用于特定的图论问题。 16. **稳定婚姻问题**：求解稳定婚姻分配问题，确保没有一对更愿意彼此结婚的夫妻。 17. **拓扑排序**：对有向无环图进行排序，使得每条有向边指向的节点都在它之前。 18. **无向图连通分支**：通过DFS或BFS找出图的连通分支。 19. **有向图强连通分支**：检测有向图的强连通分量。 20. **有向图最小点基**：寻找有向图的最小点基，即最小的节点集合，使得每个节点都可以到达至少一个点基内的节点。 21. **FLOYD算法**：计算所有节点对之间的最短路径，也可用于查找最小环。 二、网络流算法： 22. **二分图匹配**：通过匈牙利算法（DFS、BFS或HOPCROFT-CARP算法）找到最大匹配，用于资源分配等问题。 23. **无向图最小割**：寻找能够分割图的最小边集。 24. **有上下界的最小(最大)流**：在网络流中考虑边的容量限制，求解最大流或最小割。 25. **DINIC算法**：求解最大流，时间复杂度为O(V^2*E)。 26. **HLPP算法**：高效的最大流算法，时间复杂度为O(V^3)。 27. **最小费用流**：同时考虑流量和费用，寻找总费用最低的流。 28. **最佳边割集、最佳点割集、最小边割集、最小点割集**：寻找不同类型的割集，用于网络优化问题。 29. **最小路径覆盖**：找出覆盖所有边的最小路径集合。 30. **最小点集覆盖**：寻找覆盖所有边的最小节点集合。 三、数据结构算法： 31. **求某天是星期几**：基于日期计算星期的方法。 32. **左偏树**：一种自平衡的二叉堆，用于高效合并操作。 33. **树状数组**：用于动态维护区间和，支持快速查询和更新。 34. **二维树状数组**：扩展树状数组以处理二维区间的问题。 35. **TRIE树**：用于字符串的高效存储和查询，包括K叉和左儿子右兄弟两种变体。 36. **后缀数组**：用于处理字符串的后缀，支持快速的模式匹配和最长公共前后缀查找。 37. **RMQ（Range Minimum Query）**：查询给定区间内最小值，包括在线和离线算法。 这份模板提供了ACM竞赛中常见的图论、网络流和数据结构问题的算法解决方案，对于参赛者来说是极好的学习和参考资源。