本文主要是介绍简单算法板子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最短路https://www.luogu.com.cn/problem/B3647
Floyd算法
核心代码块
`void floyd()
{int i, j, k; // i和j是起始和结束节点，k是中间节点for (k = 1; k <= n; k++){for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){// 如果通过k节点的路径比当前i到j的路径短，那么更新g[i][j]if (g[i][k] != INF && g[k][j] != INF && g[i][j] > g[i][k] + g[k][j]){g[i][j] = g[i][k] + g[k][j];}}}}
}`
首先要初始化图的邻接矩阵
`for (i = 1; i <= n; i++) // 初始化图的邻接矩阵
{for (j = 1; j <= n; j++){// 对角线上的元素为0，其他元素为无穷大if (i == j){g[i][j] = 0;}else{g[i][j] = INF;}}
}`
然后需要对重边进行选择
`for (i = 0; i < m; i++)
{scanf("%d %d %d", &u, &v, &w);if (g[u][v] > w) // 由于可能存在重边，我们需要保留权值最小的那条边{g[u][v] = w;g[v][u] = w;}
}`
最小生成树
模板
定义
`#include <stdlib.h>`
`typedef struct // 定义边的结构体
{int u, v, w;
}Edge;
Edge edges[MAXM]; // 存储所有的边
int pa[MAXN]; // 并查集数组，用于判断两个节点是否在同一棵树中
int N, M; // N是节点数，M是边数
int cmp(Edge a, Edge b); // 边的比较函数，按照边的权重从小到大排序
int find(int x); // 并查集的查找函数，用于查找节点x的根节点
int kruskal(); // Kruskal算法函数
调用Kruskal算法
`int res = kruskal(); // 调用Kruskal算法计算最小生成树的权重
if (res == -1) // 如果图不连通
{printf("orz\n");
}
else
{printf("%d\n", res);
}`
边的比较函数
`int cmp(Edge a, Edge b) // 边的比较函数，按照边的权重从小到大排序
{return (a.w - b.w);
}`
并查集的查找函数
`int find(int x) // 并查集的查找函数，用于查找节点x的根节点
{while (pa[x] != x){x = pa[x];}return x;
}`
Kruskal算法函数
`int kruskal() // Kruskal算法函数
{int i, j;for (i = 0; i < M; i++) // 将所有的边按照从小到大排序{for (j = i + 1; j < M; j++){if (cmp(edges[i], edges[j]) > 0){Edge temp = edges[i];edges[i] = edges[j];edges[j] = temp;}}}for (i = 1; i <= N; i++) // 初始化并查集{pa[i] = i;}int res = 0; // 存储最小生成树的权重int cnt = 0; // 存储当前已经选择的边的数量for (i = 0; i < M; i++) // 遍历所有的边{int u = find(edges[i].u); // 边的一个节点int v = find(edges[i].v); // 边的另一个节点// 如果两个节点不在同一棵树中，说明这条边可以添加到最小生成树中if (u != v){res += edges[i].w; // 更新最小生成树的权重pa[u] = v; // 合并两棵树cnt++; // 更新已经选择的边的数量}}if (cnt != N - 1) // 如果选择边的数量小于N - 1，说明图不连通{return -1;}return res; // 返回最小生成树的权重
}
线性dp
模板
定义
`#include <stdlib.h>int max(int a, int b); // 用于比较两个数的大小的函数`
`int dp[MAX][MAX]; // 定义一个二维数组，用于存储金字塔和动态规划的状态`
核心代码段
`for (i = r - 1; i >= 1; i--) // 从倒数第二行开始，逐行向上
{for (j = 1; j <= i; j++){// 选择下方或者右下方的较大值，然后加上当前位置的值dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);}
}
# 搜索剪枝与记忆化搜索
模板
定义
`int max(int a, int b); // 求两个数的最大值
int dfs(int x, int y); // 深度优先搜索
#define MAX 10000
int R, C; // 区域的行数和列数
int height[MAX][MAX]; // 存储每个点的高度
int dp[MAX][MAX]; // 存储每个点的最长滑坡长度
int dx[4] = {-1, 1, 0, 0}; // 行
int dy[4] = {0, 0, -1, 1}; // 列`
动态规划
`or (i = 0; i < R; i++) // 对每个点进行深度优先搜索
{for (j = 0; j < C; j++){longest = max(longest, dfs(i, j)); // 更新最长滑坡长度}
}`
深度优先搜索
`int dfs(int x, int y) // 深度优先搜索
{int i, nx, ny;if (dp[x][y] != 0) // 如果已经计算过该点的最长滑坡长度，则直接返回{return dp[x][y];}dp[x][y] = 1; // 初始化为1，表示至少有一个点（及自身）for (i = 0; i < 4; i++) // 遍历四个方向{nx = x + dx[i];ny = y + dy[i];// 如果新的点在区域内，并且高度小于当前点的高度if (nx >= 0 && nx < R && ny >= 0 && ny < C && height[nx][ny] < height[x][y]){dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1); // 更新当前点的最长滑坡长度}}return dp[x][y]; // 返回当前点的最长滑坡长度
}`
# 搜索
深度优先搜索
模板
定义
`void dfs(int x, int y); // 深度优先搜索函数`
`int dx[4] = {-1, 0, 1, 0}; // 定义四个方向的移动，上右下左int dy[4] = {0, 1, 0, -1}; // 上右下左`
核心代码段
`void dfs(int x, int y) // 深度优先搜索函数
{int i, nx, ny;if (x == FX && y == FY) // 如果到达终点{ans++; // 找到一条路径，方案数加一return; // 一旦找到目标，停止搜索，回溯到上一步，然后尝试其他可能的路径}for (i = 0; i < 4; i++) // 尝试四个方向的移动{nx = x + dx[i];ny = y + dy[i];// 判断新位置是非在迷宫内，且没有被访问过，且不是障碍if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && visited[nx][ny] == 0 && maze[nx][ny] == 0){visited[nx][ny] = 1; // 标记为已访问dfs(nx, ny); // 从新位置继续深度搜索visited[nx][ny] = 0; // 搜索完后，标记为未访问}}
}
广度优先搜索
模板
定义
`void bfs(int n, int m, int x, int y);`
`int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; // 马可以移动的8 个方向int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};`
`int queue[MAX * MAX][2]; // 定义队列，用于存储待访问的位置`
核心代码段
`void bfs(int n, int m, int x, int y)
{int i, j;for (i = 0; i < n; i++) // 初始化棋盘，所有位置的步数都设为-1{for (j = 0; j < m; j++){board[i][j] = -1;}}board[x][y] = 0; // 马的初始位置的步数设为0int front = 0, rear = 0; // // 创建队列，并将马的初始化位置加入队列queue[rear][0] = x; // 新元素总是被添加到到尾部queue[rear++][1] = y; // 是储存到同一个位置，并且rear++（后置递增操作）使得尾部位置向后移动一位，为下一个元素的添加做好准备while (front != rear) // 当队列不为空时（头部位置不等于尾部位置），进入循环{x = queue[front][0]; // 取出队列的第一个元素 y = queue[front++][1]; // 并将头部位置向后移动一位，为下一个元素的处理做好准备for (i = 0; i < 8; i++) // 遍历马可以移动的所有位置{int nx = x + dx[i], ny = y + dy[i];// 检查新位置是否在棋盘内，并且是否已经被访问过if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == -1){queue[rear][0] = nx; // 将新位置加入队列，并更新步数queue[rear++][1] = ny;board[nx][ny] = board[x][y] + 1;}}}
}
# 数论基础
快速幂
模板
定义
`#include <stdlib.h>`
核心代码段
`long long a, b, p, ans,x , y;
scanf("%lld %lld %lld", &a, &b, &p);
x = a;
y = b;
ans = 1;
x = x % p;while (y > 0)
{if ((y % 2) == 1){ans = (ans * x) % p;}y = y / 2;x = (x * x) % p;
}
printf("%lld^%lld mod %lld=%lld", a, b, p, ans);
线性筛素数
模板
定义
`#include <stdlib.h>#include <math.h>void S(); // 用筛法找出所有小于n的素数`
`int prime[MAX], cnt = 0; // prime数组用于存储所有小于n的素 数，cnt用于记录素数的数量int isPrime[MAX] = {0}; // isPrime数组用于标记每个数是否为素数，0表示是素数，1表示不是素数`
主函数片段
`S(); // 找出所有小于n的素数for (i = 1; i <= q; i++) // 输出第k小的素数
{scanf("%lld", &k);printf("%lld\n", prime[k - 1]);
}`
核心代码片段
`void S() // 用筛法找出所有小于n的素数
{long long limit, i, j;limit = sqrt(n) + 1;for (j = 2; j <= limit; j++){if (isPrime[j] == 0) // 如果j是素数，则将所有p的倍数标记为非素数{for (i = j * j; i <= n; i += j){isPrime[i] = 1;}}}for (j = 2; j <= n; j++) // 将所有标记为素数的数存入prime数组{if (isPrime[j] == 0){prime[cnt++] = j;}}
}
# 邻接表数据结构
- to[i]:用于表示编号为i的终点的边
- nxt[i]:用于表示编号为i的边的下一条边的编号
- head[i]:用于表示节点编号为i的第一条边的编号
有关邻接表的题：洛谷P5908
核心代码块
添加边函数
`void add(int u, int v) // add函数用于添加边
{to[++cnt] = v; // v表示边的终点nxt[cnt] = head[u];head[u] = cnt; // 节点u的第一条边的编号
}`
与深度优先搜索相联系
核心代码块
dfs函数
`void dfs(int u) // 深度优先搜索
{int i, v;vis[u] = 1; // 标记已经访问过for (i = head[u]; i != 0; i = nxt[i]) // 用于遍历节点u的所有边{v = to[i]; // 获取当前边的终点if (vis[v] == 1) // 节点v是否已经被访问{continue; // 跳过当前循环，处理下一条边}dis[v] = dis[u] + 1; // 计算节点v到起始节点的距离dfs(v);if (dis[v] <= d){ans++;}}
}`
背包
01背包
模板
定义
`int max(int a, int b); // 用于判断两个数的大小的函数`
`int dp[MAX]; // dp[j]表示总重量不超过j时的最大价值`
核心代码段
`for (i = 1; i <= N; i++) // 用动态规划来计算最大值
{// 如果当前物品可以放入背包，那么尝试放入，并更新dp数组for (j = M; j >= W[i]; j--){dp[j] = max(dp[j], dp[j - W[i]] + D[i]);}
}
二维背包
模板
定义
`int max(int a, int b);#define MAX 1000int dp[MAX][MAX];`
动态规划
`for (i = 1; i <= n; i++) // 动态规划
{for (j = h; j >= H[i]; j--){for (k = t; k >= T[i]; k--){dp[j][k] = max(dp[j][k], dp[j - H[i]][k - T[i]] + K[i]);}}
}
# 结构体的定义
代码段
`typedef struct Node
{int floor; // 当前楼层int steps; // 到达当前楼层所需的步数
} Node;`
详细解释
- typedef：这是一个关键字，用于为数据类型定义一个新的名称。在这里，它用于为结构体定义一个新的名称，这样就可以直接使用Node而不是struct Node来声明该类型的变量。
- struct Node：这定义了一个新的结构体类型名为Node。结构体是一种复合数据类型，它允许你将多个不同类型的数据项组合成一个单一的类型。
- 在{}内部：
- int floor:这是结构体的第一个成员，名为floor，类型为int
- int steps:这是结构体的第二个成员
- Node：在typedef语句的最后，Node是新的类型名。这意味着在之后的代码中，你可以直接使用Node来声明该结构体的变量，而不需要每次都写struct Node。
并查集
并查集的操作
初始化：在进行操作前，每个元素的根节点都是它自己
`for (i = 1; i <= N; i++) // 初始化并查集
{pa[i] = i; // 每个元素所在的集合编号都是他自己
}`
查询：查询某个元素对应的树的根节点，用于判断两个元素是否属于同一集合，在查询过程中，还进行着路径的压缩
`int find(int x) // 找到元素x的根节点
{if (pa[x] != x){pa[x] = find(pa[x]);}return pa[x];
}`
合并：合并两个元素所属集合
`void un(int x, int y) // 合并元素x和元素y所在的集合
{int rootX = find(x);int rootY = find(y);if(rootX != rootY){pa[rootX] = rootY;}
}`
并查集与最小生成树的应用（洛谷P1111）
最小生成树首先要定义一个结构体
`typedef struct // 边的数据结构
{int u, v, w;
} Edge;
Edge edge[MAX];`
然后按照边的权重对边进行排序
`// qsort：要排序的数组名字
// M：数组中元素的数量
// sizeof(Edge)：数组中每个元素的大小
// cmp：比较函数，用于确定排序的顺序
qsort(edge, M, sizeof(Edge), cmp); // 使用cmp函数，按照边的权重对edge数组进行排序`
cmp函数，边的比较函数，用于排序
`int cmp(const void *a, const void *b) // 边的比较函数，用于排序
{return ((Edge *)a) -> w - ((Edge *)b) -> w;
}`
核心代码块
检查两个节点的父节点是否相同，若不相同，则表明构不成环，可以合并
`for (i = 0; i < M; i++)
{if (find(edge[i].u) != find(edge[i].v)) // 两个节点的父节点不同{un(edge[i].u, edge[i].v);maxW = edge[i].w;}
}`
判断这个图连不连通
`for (i = 2; i <= N; i++) // 判断所有的节点是否在同一个集合中
{if (find(i) != find(1)) // 如果他们的根节点不同，节点i和节点1不在同一个集合中{printf("-1\n"); // 未形成一个连通的生成树return 0;}
}
printf("%d\n", maxW); // 如果所有的节点都在一个集合中，输出最大权重`
这篇关于简单算法板子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
