2.16日学习总结

题目一：

AC代码 ： #include <stdio.h> #include <stdlib.h> #include <limits.h> #define I INT_MAX #define M 3005 #define N 2005 int n, m, t, s; // n 表示点数，m 表示边数，t 用于边的计数，s 存储最小生成树的总权值 int h[N], d[N], v[N]; // h 为链式前向星的头数组，d 存储各点到当前最小生成树的最小距离，v 标记点是否已加入最小生成树 // 定义链式前向星的边结构体 typedef struct { int o, n; // o 表示边的终点，n 指向下一条边 int w; // w 表示边的权值 } E; E e[M << 1]; // 存储边的数组 // 链式前向星的加边操作 void a(int x, int y, int z) { e[++t].o = y; e[t].w = z; e[t].n = h[x]; h[x] = t; } // Prim 算法 void p() { int i, u = 1; // u 表示当前正在处理的点 // 初始化距离数组 for (i = 1; i <= n; i++) { d[i] = I; } d[1] = 0; // 初始化第一个点连接的边的距离 for (i = h[1]; i; i = e[i].n) { if (e[i].w < d[e[i].o]) { d[e[i].o] = e[i].w; } } // 循环 n - 1 次，构建最小生成树 for (i = 1; i < n; i++) { int m = I; // m 存储当前最小的边权 v[u] = 1; // 标记当前点已加入最小生成树 // 找到距离最小生成树最近且未加入的点 for (int j = 1; j <= n; j++) { if (!v[j] && d[j] < m) { u = j; m = d[j]; } } s += m; // 将最小边权累加到总权值中 // 更新与新加入点相连的点到最小生成树的距离 for (int k = h[u]; k; k = e[k].n) { int o = e[k].o; if (!v[o] && e[k].w < d[o]) { d[o] = e[k].w; } } } } int main() { scanf("%d %d", &n, &m); // 读取边的信息并添加到图中 while (m--) { int x, y, z; scanf("%d %d %d", &x, &y, &z); a(x, y, z); a(y, x, z); } p(); // 执行 Prim 算法 printf("%d\n", s); // 输出最小生成树的总权值 return 0; } 题解： 

1.limits.h：引入 INT_MAX，表示整数的最大值，这里用宏定义 I 来表示无限大，用于后续初始化距离数组。

2. 全局变量定义 int n, m, t, s; int h[N], d[N], v[N]; typedef struct { int o, n; int w; } E; E e[M << 1];

 n：表示图的顶点数量。

m：表示图的边数量。

t：用于链式前向星中边的计数。

s：存储最小生成树的总权值。

h[N]：链式前向星的头数组，用于存储每个顶点的第一条边的编号。

d[N]：存储每个顶点到当前最小生成树的最小距离。

v[N]：标记数组，用于标记每个顶点是否已经被加入到最小生成树中。

E 结构体：定义链式前向星中的边，o 表示边的终点，n 指向下一条边的编号，w 表示边的权值。

e[M << 1]：存储所有边的数组，M << 1 等价于 M * 2，因为是无向图，每条边需要存储两次。

3. 加边函数 a void a(int x, int y, int z) { e[++t].o = y; e[t].w = z; e[t].n = h[x]; h[x] = t; }

 该函数用于将一条边加入到链式前向星中。

e[++t]：先将边的计数器 t 加 1，然后使用新的编号存储这条边。

e[t].o = y：将边的终点设为 y。

e[t].w = z：将边的权值设为 z。

e[t].n = h[x]：将当前边的下一条边指向顶点 x 原来的第一条边。

h[x] = t：将顶点 x 的第一条边更新为当前边。

4.Prim 算法函数 p void p() { int i, u = 1; // 初始化距离数组 for (i = 1; i <= n; i++) { d[i] = I; } d[1] = 0; // 初始化第一个点连接的边的距离 for (i = h[1]; i; i = e[i].n) { if (e[i].w < d[e[i].o]) { d[e[i].o] = e[i].w; } } // 循环 n - 1 次，构建最小生成树 for (i = 1; i < n; i++) { int m = I; v[u] = 1; // 找到距离最小生成树最近且未加入的点 for (int j = 1; j <= n; j++) { if (!v[j] && d[j] < m) { u = j; m = d[j]; } } s += m; // 更新与新加入点相连的点到最小生成树的距离 for (int k = h[u]; k; k = e[k].n) { int o = e[k].o; if (!v[o] && e[k].w < d[o]) { d[o] = e[k].w; } } } }

初始化部分：

将所有顶点到最小生成树的距离 d[i] 初始化为无限大 I，将第一个顶点的距离 d[1] 设为 0，表示从这个顶点开始构建最小生成树。

遍历第一个顶点的所有邻接边，更新这些邻接顶点到最小生成树的距离。

构建最小生成树部分：

进行 n - 1 次循环，因为最小生成树的边数等于顶点数减 1。

在每次循环中，先将当前顶点 u 标记为已加入最小生成树。

遍历所有顶点，找到距离最小生成树最近且未加入的顶点 u，并记录最小距离 m。

将最小距离 m 累加到总权值 s 中。

遍历新加入顶点 u 的所有邻接边，更新这些邻接顶点到最小生成树的距离。

复杂度分析

时间复杂度：Prim 算法的时间复杂度为 ，其中  是顶点的数量。因为在每次循环中，需要遍历所有顶点来找到距离最小生成树最近的顶点。

空间复杂度：主要的空间开销是存储边和顶点信息的数组，空间复杂度为 ，其中  是顶点数量， 是边的数量。

总结：

最小生成树问题是图论中的经典问题，对于一个连通加权无向图，需要找出一个包含图中所有顶点的树，并且这棵树的所有边的权值之和最小。在题中，输入会给出图的顶点数 n 和边数 m，以及每条边的两个端点和边的权值，我们需要通过 Prim 算法计算出这个图的最小生成树的边权总和。

使用 Prim 算法来解决这个问题。Prim 算法的核心思想是从图中任意一个顶点开始，逐步扩展生成树，每次选择与当前生成树相连的边中权值最小的边，并将这条边的另一个端点加入到生成树中，直到所有顶点都被加入到生成树为止。

题目二：

AC代码：  #include <stdio.h> #include <stdlib.h> #define M 200010 #define L long long int n, m; int a[M], h[M], q[M]; typedef struct { int x, y, k, i; } N; N b[M], c[M]; // 按照 x 排序的比较函数 int cx(const void *A, const void *B) { N *pa = (N *)A; N *pb = (N *)B; if (pa->x == pb->x) { return pa->y - pb->y; } return pa->x - pb->x; } // 按照 y 排序的比较函数 int cy(const void *A, const void *B) { N *pa = (N *)A; N *pb = (N *)B; if (pa->y == pb->y) { return pb->k - pa->k; } return pa->y - pb->y; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].k); c[i] = b[i]; b[i].i = c[i].i = i; } qsort(b + 1, m, sizeof(N), cx); qsort(c + 1, m, sizeof(N), cy); h[n] = a[n]; for (int i = n - 1; i >= 1; i--) { h[i] = (h[i + 1] < a[i]) ? h[i + 1] : a[i]; } q[1] = a[1]; for (int i = 2; i <= n; i++) { q[i] = (q[i - 1] < a[i]) ? q[i - 1] : a[i]; } int l = 1, r = m, t = 0; L s = 0; while (r >= 1) { int nr = b[r].k - t; int nl = c[l].k - t; int nt = (nl < nr) ? nl : nr; s += (L)nt * h[b[r].x] + (L)nt * q[c[l].y]; t += nt; while (r >= 1 && b[r].k <= t) { r--; } while (l <= m && c[l].k <= t) { l++; } } s -= q[c[1].y]; printf("%lld\n", s); return 0; } 题解： 

1.stdlib.h：提供 qsort 函数，用于对数组进行排序。

2.全局变量定义 int n, m; int a[M], h[M], q[M]; typedef struct { int x, y, k, i; } N; N b[M], c[M];

n：表示数组 a 的长度。

m：表示三元组的数量。

a[M]：存储输入的数组元素。

h[M]：存储数组 a 的后缀最小值，即从每个位置开始到数组末尾的最小值。

q[M]：存储数组 a 的前缀最小值，即从数组开头到每个位置的最小值。

N 结构体：用来存储三元组信息，x 和 y 是区间相关的位置，k 是一个计数相关的值，i 是编号。

b[M] 和 c[M]：分别存储三元组，会按照不同规则进行排序。

3.排序比较函数 // 按照 x 排序的比较函数 int cx(const void *A, const void *B) { N *pa = (N *)A; N *pb = (N *)B; if (pa->x == pb->x) { return pa->y - pb->y; } return pa->x - pb->x; } // 按照 y 排序的比较函数 int cy(const void *A, const void *B) { N *pa = (N *)A; N *pb = (N *)B; if (pa->y == pb->y) { return pb->k - pa->k; } return pa->y - pb->y; }

cx 函数：用于对三元组按照 x 进行排序，如果 x 相等，则按照 y 从小到大排序。

cy 函数：用于对三元组按照 y 进行排序，如果 y 相等，则按照 k 从大到小排序。

4.主函数  scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].k); c[i] = b[i]; b[i].i = c[i].i = i; }

 首先读取 n 和 m 的值。

接着读取数组 a 的 n 个元素。

然后读取 m 个三元组，将其存储在 b 数组中，同时复制一份到 c 数组，并为每个三元组赋予编号。

排序部分 qsort(b + 1, m, sizeof(N), cx); qsort(c + 1, m, sizeof(N), cy);

 使用 qsort 函数对 b 数组按照 x 排序，对 c 数组按照 y 排序。

计算前缀和后缀最小值 h[n] = a[n]; for (int i = n - 1; i >= 1; i--) { h[i] = (h[i + 1] < a[i]) ? h[i + 1] : a[i]; } q[1] = a[1]; for (int i = 2; i <= n; i++) { q[i] = (q[i - 1] < a[i]) ? q[i - 1] : a[i]; }

 计算后缀最小值 h 数组，从数组末尾开始往前遍历，不断更新每个位置的最小值。

计算前缀最小值 q 数组，从数组开头开始往后遍历，不断更新每个位置的最小值。

核心 int l = 1, r = m, t = 0; L s = 0; while (r >= 1) { int nr = b[r].k - t; int nl = c[l].k - t; int nt = (nl < nr) ? nl : nr; s += (L)nt * h[b[r].x] + (L)nt * q[c[l].y]; t += nt; while (r >= 1 && b[r].k <= t) { r--; } while (l <= m && c[l].k <= t) { l++; } }

 使用双指针 l 和 r 分别指向 c 数组和 b 数组的起始和末尾位置。

t 用于记录已经处理的计数总和。

s 用于存储最终结果。

在每次循环中，计算 nr 和 nl 分别表示当前三元组还未处理的计数，取两者较小值 nt。

将 nt 乘以对应位置的后缀最小值和前缀最小值并累加到 s 中。

更新 t 的值，同时移动指针 l 和 r，跳过已经处理完的三元组。

结果调整与输出  s -= q[c[1].y]; printf("%lld\n", s);

 对结果 s 进行调整，减去 q[c[1].y]。

输出最终结果 s。

总结：

输入包含一个长度为 n 的数组 a，以及 m 个三元组 (x, y, k)。需要根据这些信息，结合数组 a 的前缀最小值和后缀最小值，计算出一个最终的结果 ans。整体思路是先对输入的三元组按照不同规则排序，接着计算数组 a 的前缀最小值和后缀最小值，最后通过双指针的方式遍历这些三元组，逐步累加计算结果，最后进行一些调整。