给一个差不多的代码
思路:
通过dfs找到最小生成树中任意两点之间所经过的路径的最大值和次大值 (建议自己画个图理解下)
(比如从a走到e可能经过b c d, 现在就是要找到从a 到 e上的最大值和次大值)
(这里我们定义不在树中的边Line连接着点a b, 最近公共祖先节点是LCA)
找到点a和b的LCA(最近公共祖先)
在a 和 b分别走到LCA上时候会产生两对最大值和次大值(边从 a -> LCA 和 b -> LCA两条边, 每条边会分别产生一对)
然后再次求出这四个值中的最大值和次大值
如果最大值小于Line(遍历到的不在树中的边)的权值,就替换成最大值,否则如果大于次大值则替换次大值;
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int p[N];
int fa[N][32], deep[N];
int d1[N][32], d2[N][32]; //d1表示最大值 d2表示次大值
int e[N * 2], ne[N * 2], h[N], w[N * 2], idx;
struct Edge
{
int a, b, w;
bool f;
bool operator < (const Edge W) const
{
return w < W.w;
}
}edge[M];
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
//求最小生成树 以及判断边是否在生成树中 顺便建个图(邻接表)
ll kurskal()
{
for (int i = 1; i <= n; i++) p[i] = i;
memset(h, -1, sizeof h);
ll sum = 0;
for (int i = 0; i < m; i++)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
int pa = find(a), pb = find(b);
if (pa != pb)
{
p[pa] = pb;
edge[i].f = true;
add(a, b, w), add(b, a, w);
sum += w;
}
}
return sum;
}
//求最小生成树中的最大值和次大值(和y总讲的一样)
void dfs(int u, int father)
{
fa[u][0] = father;
deep[u] = deep[father] + 1;
for (int i = 1; i <= 31; i++)
{
int anc = fa[u][i - 1];
fa[u][i] = fa[anc][i - 1];
int distance[4] = { d1[u][i - 1], d2[u][i - 1], d1[anc][i - 1], d2[anc][i - 1] };
d1[u][i] = d2[u][i] = -INF;
for (int k = 0; k < 4; k++)
{
int t = distance[k];
if (t > d1[u][i]) d2[u][i] = d1[u][i], d1[u][i] = t;
else if (t > d2[u][i] && t != d1[u][i]) d2[u][i] = t;
}
}
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
d1[j][0] = w[i], d2[j][0] = -INF;
dfs(j, u);
}
}
//只求lca节点
int lca(int x, int y)
{
if (deep[y] > deep[x]) swap(x, y);
for (int i = 31; i >= 0; i--)
if (deep[fa[x][i]] >= deep[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 31; i >= 0; i--)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
//每次只求树中一个方向的最大值和次大值
//再带入另一个方向后就能求出两个方向上一起的最大值和次大值
void qmax(int x, int y, int& max1, int& max2)
{
if (deep[y] > deep[x]) swap(x, y);
for (int i = 31; i >= 0; i--)
if (deep[fa[x][i]] >= deep[y])
{
int dis[2] = { d1[x][i], d2[x][i] };
for (int k = 0; k < 2; k++)
{
int w = dis[k];
if (w > max1) max2 = max1, max1 = w;
else if (w > max2 && w != max1) max2 = w;
x = fa[x][i];
}
}
return;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edge[i] = { a, b, w };
}
sort(edge, edge + m);
ll sum = kurskal();
//lca预处理
deep[1] = 1;
d1[1][0] = d2[1][0] = INF;
dfs(1, -1);
//lca处理出任意两点路径之间的最大值, 次大值
ll ans = 1e18;
for (int i = 0; i < m; i++) //这里是访问没在生成树中的边
if (!edge[i].f)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
ll t;
int max1 = -INF;
int max2 = -INF;
int LCA = lca(a, b);
//分别从lca节点两个方向更新
qmax(a, LCA, max1, max2);
qmax(b, LCA, max1, max2);
if (w > max1)
t = sum + w - max1;
else if (w > max2)
t = sum + w - max2;
ans = min(ans, t);
}
cout << ans << endl;
return 0;
}
tql %%%