ACM竞赛必备：C语言算法集合

"该资源是一个ACM/ICPC竞赛相关的C程序集，包含了各种算法，适合准备此类竞赛的选手学习。主要包括图论、网络流和数据结构等方面的问题解决方法。" 详细说明: 这个C程序集重点围绕三个方面展开：图论、网络流和数据结构。 在图论部分，涉及多种经典算法： 1. DAG的深度优先搜索标记：用于识别有向无环图(DAG)中的特定属性。 2. 无向图找桥：找到图中能切断连通性的关键边。 3. 无向图连通度(割)：确定图中各个连通分量。 4. 最大团问题：寻找图中最大的完全子图。 5. 欧拉路径：找到从一个顶点出发并经过所有边返回原点的路径。 6. Dijkstra算法：计算图中两点间的最短路径，这里分别给出了数组实现和优化版本。 7. Bellman-Ford算法：处理负权边的单源最短路径问题。 8. SPFA算法：一种基于队列的短路径快速算法。 9. 第K短路：找到除了最短路径外的第K短路径。 10. Prim算法：构建最小生成树(MST)。 11. 次小生成树：找到第二小的生成树。 12. 最小生成森林：处理多棵最小生成树的情况。 13. 有向图最小树形图：构建有向图的最小树形图。 14. Tarjan算法：用于查找强连通分量。 15. 弦图判断及完美消除点排列：处理弦图相关问题。 16. 稳定婚姻问题：应用Gale-Shapley算法解决分配问题。 17. 拓扑排序：对有向无环图进行排序。 18. 无向图和有向图的连通分支：利用DFS或BFS算法找出图的连通分支。 19. 有向图最小点基：寻找图的最小点基。 20. Floyd算法：寻找所有点对之间的最短路径，同时可检测负权环。 在网络流部分： 1. 二分图匹配：采用匈牙利算法，包括DFS和BFS实现，以及Hopcroft-Carp算法。 2. Kuhn-Munkres算法：高效求解二分图最佳匹配。 3. 无向图最小割：分割图的最小代价方式。 4. 有上下界限制的最小(最大)流：处理流量有上限和下限的网络流问题。 5. Dinic算法：实现最大流问题，具有较好的效率。 6. HLPP算法：另一种求解最大流的方法。 7. 最小费用流：考虑边的费用，寻找总费用最低的流。 8. 最小费用流的优化版本：进一步提升效率。 9. 最佳边割集、最佳点割集和最小边/点割集：处理割集问题，特别是点连通度的计算。 10. 最小路径覆盖：找到覆盖所有边的最小路径集合。 11. 最小点集覆盖：寻找覆盖所有边的最小顶点集。 在数据结构部分： 1. 求某天是星期几：解决日期转换问题。 2. 左偏树：一种特殊的二叉堆，常用于平衡操作。 3. 树状数组：高效处理区间查询和更新操作。 4. 二维树状数组：扩展树状数组以处理二维区间问题。 5. Trie树：前缀树，用于存储字符串并进行查找。 6. 后缀数组：处理字符串的后缀，可用于模式匹配等。 7. 后缀数组的优化算法：如线性时间复杂度的构建方法。 8. RMQ(Range Minimum Query)：区间最小值查询，有在线和离线算法。 这个程序集全面覆盖了ACM/ICPC竞赛中常见的算法，对于提高编程竞赛技能和理解算法有着极大帮助。