acm常用算法模板

### ACM常用算法模板详解 #### 一、Union-FindSets（并查集） **定义：** 并查集是一种数据结构，用于处理一些不交集的合并及查询问题，常常用来解决图论中的连通性问题。 **核心操作：** 1. **Make_Set：** 创建一个新的集合。 ```cpp void make_set(long node[], long rank[], long size) { for (long i = 1; i <= size; i++) { node[i] = i; rank[i] = 0; } } ``` 2. **Find_Set：** 查找元素所属的集合。 ```cpp long find_set(long node[], long x) { long px = x; while (x != node[x]) x = node[x]; // 路径压缩 long p; while (px != node[px]) { p = node[px]; node[px] = x; px = p; } return x; } ``` 3. **Merge：** 合并两个集合。 ```cpp bool merge(long node[], long rank[], long x, long y) { x = find_set(x); y = find_set(y); if (x == y) return false; if (rank[x] < rank[y]) node[x] = y; else { node[y] = x; if (rank[x] == rank[y]) rank[x]++; } return true; } ``` #### 二、BFS（广度优先搜索） **用途：** 常用于求解最短路径问题。 **实现：** ```cpp int bfs(int a, int b) { int q[N], step[N], front = 0, rear = 0, k, tmp; fill(step, step + N, -1); q[rear++] = a; step[a] = 0; while (rear != front) { k = q[front++]; tmp = k + floor[k]; if (tmp <= n && step[tmp] == -1) { if (tmp == b) return step[k] + 1; q[rear++] = tmp; step[tmp] = step[k] + 1; } tmp = k - floor[k]; if (tmp >= 1 && step[tmp] == -1) { if (tmp == b) return step[k] + 1; q[rear++] = tmp; step[tmp] = step[k] + 1; } } return -1; } ``` #### 三、DFS（深度优先搜索） **用途：** 用于解决迷宫问题等递归问题。 **实现：** ```cpp struct maze { char g[7][7]; int si, sj; int di, dj; int wall; }; maze map; int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int N, M, T; bool flag; void dfs(int x, int y, int n) { if (flag == 1) return; int temp = T - n - abs(map.di - x) - abs(map.dj - y); if (temp < 0 || temp % 2 == 1) return; for (int i = 0; i < 4; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; if (n == T - 1 && map.g[dx][dy] == 'D') { flag = true; return; } if (map.g[dx][dy] == '.' && (dx >= 0 && dx < N && dy >= 0 && dy < M)) { ``` #### 四、Prim算法求最小生成树 **原理：** Prim算法通过贪心策略逐步构建最小生成树，每次选择代价最小且能连接新顶点的边。 **步骤：** 1. 初始化一个空的最小生成树。 2. 从任意顶点开始，找到与该顶点相邻的未加入最小生成树中的顶点，并且该边权重最小。 3. 将这个顶点和对应的边加入最小生成树。 4. 重复步骤2和3，直到所有顶点都被包含在内。 #### 五、Kruskal算法求最小生成树 **原理：** Kruskal算法也是通过贪心策略逐步构建最小生成树，但它是按边的权重排序后依次考虑加入最小生成树中，同时确保加入的边不会形成环。 **步骤：** 1. 将所有的边按照权重从小到大排序。 2. 依次考虑每条边，如果这条边的两端不在同一个集合中，则将这条边加入最小生成树，并将这两个端点所在的集合合并。 3. 重复步骤2，直到最小生成树包含所有顶点。 #### 六、Dijkstra算法求单源最短路径 **原理：** Dijkstra算法是一种贪心算法，它维护了一个从源点到当前已知最近的顶点的距离列表，并不断更新这些距离。 **步骤：** 1. 初始化距离列表，将源点到其他所有顶点的距离初始化为无穷大，源点到自身的距离为0。 2. 从未确定最短路径的顶点中选择距离最小的顶点，更新从该顶点出发可以到达的顶点的距离。 3. 重复步骤2，直到所有顶点的最短路径都确定了。 #### 七、Bellman-ford算法求单源最短路径 **原理：** Bellman-Ford算法允许存在负权边，并能够检测出是否存在负权环。 **步骤：** 1. 初始化距离列表，将源点到其他所有顶点的距离初始化为无穷大，源点到自身的距离为0。 2. 依次对每个顶点执行松弛操作，共进行|V|-1次，其中|V|是顶点数。 3. 再次执行一次松弛操作，如果距离还能被更新，则说明存在负权环。 #### 八、Floyd-Warshall算法求每对节点间最短路径 **原理：** Floyd-Warshall算法是一种动态规划算法，用于计算图中所有顶点之间的最短路径。 **步骤：** 1. 初始化距离矩阵，将所有可达的边的距离填入矩阵。 2. 遍历每一个可能作为中间顶点的顶点k。 3. 对于每一对顶点i和j，检查是否存在更短的路径i-k-j，如果是，则更新距离矩阵中i到j的距离。 #### 九、Segment Tree（线段树） **定义：** 线段树是一种高效的数据结构，用于区间查询和区间更新问题。 **应用：** 1. 区间求和 2. 区间最大值/最小值 3. 区间更新 #### 十、树状数组（Binary Indexed Tree） **定义：** 树状数组是一种支持快速前缀和查询以及单点更新的数据结构。 **应用：** 1. 前缀和查询 2. 单点更新 #### 十一、Trie（字典树） **定义：** 字典树是一种用于存储字符串的树形数据结构。 **应用：** 1. 字符串查找 2. 自动补全 #### 十二、KMP算法 **定义：** KMP算法是一种高效的字符串匹配算法，可以在O(n+m)时间内完成匹配，其中n是文本的长度，m是模式的长度。 **核心思想：** 利用已经匹配的信息避免不必要的比较。 #### 十三、Dinic算法 **定义：** Dinic算法是一种求解最大流问题的算法，特别适用于稠密图。 **核心思想：** 通过多次寻找增广路径来更新流量，每次更新后重新构造层次图，保证算法效率。 #### 十四、排序 **定义：** 排序是对一组对象按照特定顺序进行排列的过程。 **常用排序算法：** 1. 快速排序 2. 归并排序 3. 堆排序 #### 十五、精度计算——加法 **定义：** 精度计算是指处理高精度数值时的计算方法，通常涉及到位运算和循环。 #### 十六、最大公约数、最小公倍数 **定义：** 最大公约数（GCD）是指两个或多个整数共有约数中最大的一个；最小公倍数（LCM）是指两个或多个整数共有倍数中最小的一个。 **实现：** 1. 使用辗转相除法计算GCD 2. LCM可以通过GCD计算得出 #### 十七、模取幂运算 **定义：** 模取幂运算是指计算\(a^b \mod m\)的结果，常用于密码学等领域。 **实现：** 1. 快速幂算法 #### 十八、几何计算 1. **两矢量间角度** 2. **两点距离（2D、3D）** 3. **射向法判断点是否在多边形内部** 4. **判断点是否在线段上** 5. **判断两线段是否相交** 6. **判断线段与直线是否相交** 7. **点到线段最短距离** 8. **求两直线的交点** #### 十九、线性代数 1. **求解模线性方程** 2. **求解模线性方程组（中国余数定理）** #### 二十、素数相关 1. **筛法素数产生器** 2. **判断一个数是否素数** #### 二十一、STL Algorithms C++标准库提供了丰富的算法模板，如排序、查找、转换等操作，极大地简化了编程过程。