总结一下前天的次小生成树 记得之前写过次小生成树的题 但是当时没有总结 也忘记了当时是怎么做的 前天遇到了 就写了一题并学了一下两个算法

题目

https://loj.ac/p/10068

kruskal算法（不懂）

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long h[101010], f[101000], md1[1010][1010], md2[1010][1010], len = 0;
struct pp
{int u, v, w, p;bool operator<(const pp &o)const//结构体排序 {return w < o.w;}} e[101000];
struct E
{int u, w, next;
} q[101000];//邻接表 不太熟练 
int getf(int u)
{if (f[u] == u)return u;else{f[u] = getf(f[u]);return f[u];}
}
void merge(int u, int v)
{int xx = getf(u);int yy = getf(v);if (xx != yy)f[yy] = xx;
}
void add(int u, int v, int w)
{q[++len].u = v;q[len].w = w;q[len].next = h[u];h[u] = len;
}
void dfs(int u, int t, int f, int max1, int max2)
{md1[u][t] = max1;md2[u][t] = max2;for (int i = h[t]; i != -1; i = q[i].next){int v = q[i].u;int w = q[i].w;if (v != f){int t1 = max1, t2 = max2;if (w > max1)t1 = w, t2 = max1;else if (w > max2 && w < max1)t1 = max1, t2 = w;dfs(u, v, t, t1, t2);}}
}
int main()
{int i, j, k, m, n;scanf("%d%d", &n, &m);memset(h, -1, sizeof(h));//使用邻接表前初始化一下 刚开始因为对邻接表不熟练 没有初始化错了好几次 for (i = 1; i <= n; i++)f[i] = i;for (i = 1; i <= m; i++){scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);}sort(e + 1, e + 1 + m);long long sum = 0;for (i = 1; i <= m; i++){int u = e[i].u, v = e[i].v, w = e[i].w;if (getf(u) != getf(v))//用prim算法求一下最小生成树 {sum += w;merge(u, v);add(u, v, w);add(v, u, w);//如果用到了u v这两条边的关系 就把他们加入到邻接表中 e[i].p = 1;// 并标记这个边用过了  }}for (i = 1; i <= n; i++)dfs(i, i, -1, 0, 0);//用dfs更新边与边之间的 我好像还是不太明白 求的是边与边之前的最大权值吧好像 ??好烦 找视频理解一下吧！！！ 至于为什么是两个i我也不理解？还是没有完全明白 long long ans = 1e18;for (i = 1; i <= m; i++){if (e[i].p == 0)//如果这个边没有被用到 就可以尝试用这个边来更新树 {int u = e[i].u, v = e[i].v, w = e[i].w;if (w > md1[u][v])ans = min(ans, sum + w - md1[u][v]);else  if (w > md2[u][v])ans = min(ans, sum + w - md2[u][v]);}}printf("%lld\n", ans);return 0;
}

prim

还是同一道题不过这个算法过不去 但是模板是没有错的

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int e[1010][1010], f[1010], d[1010], book[1010], maxd[1010][1010], c[1010][1010];
//maxd[i][j]用来表示i到j路径里最大的边 
#define inf 0x3f3f3f
int n, sum = 0, ans = 0;
void prime()
{int i, j, k, minn;for (i = 1; i <= n; i++){d[i] = e[1][i];f[i] = 1;//把所有的节点的前驱都初始化为1 }f[1] = 0;//1节点没有前驱 d[1] = 0;for (i = 1; i <= n; i++){minn = inf;k = 0;for (j = 1; j <= n; j++){if (!book[j] && d[j] < minn)minn = d[j], k = j;}ans += d[k];c[f[k]][k] = c[k][f[k]] = 0;//标记一下这个边用过了 book[k] = 1;for (j = 1; j <= n; j++){if (book[j])maxd[j][k] = maxd[k][j] = max(maxd[j][f[k]], d[k]);// 如果当前节点用过了 就更新与她相连或间接相连的点之间的最大权值 if (!book[j] && d[j] > e[k][j]){d[j] = e[k][j];f[j] = k;//把这个节点的前驱设为k }}}
}
void sprime()
{int i, j;sum = inf;for (i = 1; i <= n; i++){for (j = i + 1; j <= n; j++){if (c[i][j] == 1 && e[i][j] != inf){sum = min(ans + e[i][j] - maxd[i][j], sum);}}}
}
int main()
{int i, j, a, b, w;int m;scanf("%d%d", &n, &m);memset(e, inf, sizeof(e));for (i = 1; i <= m; i++){scanf("%d%d%d", &a, &b, &w);e[a][b] = min(e[a][b], w);//因为可能有重边 我们要判断一下再赋值 e[b][a] = e[a][b];c[a][b] = c[b][a] = 1;}prime();sprime();printf("%d\n", sum);return 0;
}