题目
思考
代码
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 510, M = 10010;
typedef long long LL;// 定义边的结构体，包含两个顶点和权重，并重载小于运算符以便于排序
struct Edge {int a, b, w;bool f = false; // 标记是否为最小生成树的边bool operator < (const Edge & A) const {return w < A.w; // 根据权重从小到大排序}
} edge[M];// 图的邻接表表示
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int cnt;
int n, m;
// dist1 和 dist2 分别存储任意两点间的边权最大值和次大值
int dist1[N][N], dist2[N][N];
int p[N]; // 并查集的父节点数组// 添加边的函数
void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}// 并查集的查找函数，路径压缩
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);
}// 深度优先搜索（DFS）函数，用于在生成树中找到两点间的最长路径
void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[]) {d1[u] = maxd1;d2[u] = maxd2;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j != fa) { // 避免往回搜索int td1 = maxd1, td2 = maxd2;if (w[i] > td1) td2 = td1, td1 = w[i];else if (w[i] < td1 && w[i] > td2) td2 = w[i];dfs(j, u, td1, td2, d1, d2);}}
}int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 0; i < m; ++i) {int a, b, w;cin >> a >> b >> w;edge[i] = {a, b, w};}// 根据边的权重排序sort(edge, edge + m);// 初始化并查集for (int i = 1; i <= n; ++i) p[i] = i;LL sum = 0;// 使用 Kruskal 算法构建最小生成树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;sum += w;add(a, b, w);add(b, a, w);edge[i].f = true;}}// 对最小生成树中的每条边进行 DFS，以找到任意两点间的最长路径for (int i = 1; i <= n; ++i) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);LL res = 1e18;// 遍历所有非最小生成树的边，尝试替换生成树中的边以找到次小生成树for (int i = 0; i < m; ++i) {int a = edge[i].a, b = edge[i].b, w = edge[i].w;if (!edge[i].f) {LL t = 1e18;if (w > dist1[a][b]) {t = sum + w - dist1[a][b];} else if (w > dist2[a][b]) {t = sum + w - dist2[a][b];}res = min(res, t);}}cout << res << endl;return 0;
}
