ACM经典代码集锦：图论与网络流算法

"acm常用代码 超级经典的代码" 这篇资源主要涵盖了ACM（国际大学生程序设计竞赛）中常见的算法和数据结构，适用于训练和解决编程竞赛中的问题。以下是其中涉及的一些重要知识点的详细说明： 1. **Graph图论** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，深度优先搜索（DFS）用于标记节点，发现图的拓扑结构。 - **无向图找桥**：桥是指删除后会使得图不连通的边，可以使用DFS来寻找。 - **无向图连通度**：计算图的连通分量，通常用DFS或BFS实现。 - **最大团问题**：寻找图中最大的完全子图，可以用动态规划和DFS解决。 - **欧拉路径**：在有向或无向图中寻找通过所有边一次且仅一次的路径，适用于具有特定性质的图。 - **DIJKSTRA算法**：求解单源最短路径问题，有两种实现方式，一种是基于数组的O(N^2)，另一种是基于优先队列的O(E*logE)。 - **BELLMAN-FORD算法**：处理负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：Shortest Path Faster Algorithm，用于求解单源最短路径，它是一种优化的Bellman-Ford算法。 - **第K短路**：除了最短路径外，寻找第K条最短路径，可以使用Dijkstra或A*算法进行扩展。 - **PRIM算法**：最小生成树（MST）算法之一，用于找到无向图中权值最小的树形子图。 - **Kruskal算法**：另一种求MST的方法，时间复杂度为O(MlogM)，适用于稠密图。 - **最小生成森林**：处理带权有向图，寻找最小的树形子图，可能包含多棵树。 - **最小树形图**：在有向图中找到最小树形子图，用于网络设计等问题。 - **TARJAN强连通分量**：检测图中的强连通分量，即每个节点都可以到达其他所有节点的子图。 - **弦图判断**：识别图是否为弦图，弦图是指在圆上的点之间存在弦的所有边组成的图。 - **稳定婚姻问题**：用Gale-Shapley算法解决，寻找稳定的一对一匹配方案。 - **拓扑排序**：对有向无环图进行排序，使得对于每一条有向边u->v，u都在v之前。 - **无向图连通分支**：利用DFS或BFS找到图的连通分支。 - **有向图强连通分支**：找出有向图中的强连通分量，可使用DFS实现。 - **有向图最小点基**：找到有向图中最小的点集，使得从任意点到其他点都有一条路径。 2. **Network网络流** - **二分图匹配**：匈牙利算法用于寻找二分图中的最大匹配，有DFS和BFS两种实现方式。 - **HOPCROFT-KARP算法**：改进的二分图匹配算法，时间复杂度为O(M√N)。 - **KUHN-MUNKRAS算法**：求解二分图的最佳匹配，效率较高。 - **最小割**：在无向图中寻找最小的边集合，使得去掉这些边后图不连通。 - **最大流**：在网络流问题中，寻找从源点到汇点的最大流量，有Dinic算法（O(V^2*E)）和HLPP算法（O(V^3)）等。 - **最小费用流**：同时考虑流量和费用，求解最小总费用下的最大流，有多种实现方法。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集**：这些都是网络流问题的变种，用于优化特定目标。 - **最小路径覆盖**：寻找最小的边集合，使得每个顶点至少有一条路径到达其他顶点。 - **最小点集覆盖**：寻找最小的顶点集合，使得每个边至少有一个端点在集合内。 3. **Structure数据结构** - **求某天是星期几**：通常涉及到日期计算，可以使用蔡勒公式或其他方法解决。 - 其他未列出的数据结构问题，如栈、队列、链表、树、堆、图等，都是ACM竞赛中常见的基础数据结构。 这些代码库和知识点是ACM竞赛选手必备的工具，它们不仅涵盖了基本的图论和网络流算法，还涉及到一些高级的数据结构和优化技巧，对于提升编程能力和解决问题的能力非常有帮助。