#include #include using namespace std; const int N = 1e5 + 5; const int M = 2e5 + 5; const long long oo = 1e18; int n, m; int u[M], v[M], w[M], p[M]; // 边的起点、终点、权重、原始索引 int h[N], id[M], nx[M], et; // 邻接表头、边ID、下一条边、边计数器 int f[N], mark[M]; // 并查集父节点、标记边是否在MST中 long long s, ans[M]; // MST总权重、每条边对应的答案 int dep[N], pid[N]; // DFS深度、指向父节点的边ID // 比较函数，用于按边权排序 bool cmp(int x, int y) { return w[x] < w[y]; } // 并查集查找根节点（带路径压缩） int getf(int u) { return f[u] ? f[u] = getf(f[u]) : u; } // 向邻接表中添加一条边 (x -> p) void link(int x, int p) { id[++et] = p; nx[et] = h[x]; h[x] = et; } // DFS遍历MST，记录每个节点的深度和父边ID void dfs(int x, int f = 0, int p = 0) { dep[x] = dep[f] + 1; pid[x] = p; for (int i = h[x]; i; i = nx[i]) { int to = u[id[i]] ^ v[id[i]] ^ x; // 利用异或性质找到另一个端点 if (to != f) dfs(to, x, id[i]); } } int main() { scanf("%d%d", &n, &m); // 读入所有边 for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u[i], &v[i], &w[i]); p[i] = i; // 记录原始索引 } // 按边权从小到大排序边的索引 sort(p + 1, p + m + 1, cmp); // Kruskal算法构建最小生成树 for (int i = 1; i <= m; i++) { int x = u[p[i]], y = v[p[i]]; if (getf(x) == getf(y)) continue; // 已连通，跳过 mark[p[i]] = 1; // 标记该边在MST中 f[getf(x)] = y; // 合并集合 s += w[p[i]]; // 累加MST总权重 link(x, p[i]); // 建无向图（实际是双向link，但这里只建了单向？注意！） link(y, p[i]); // 【修正】原代码可能漏了这一行，应补充以建立无向图 } // 初始化答案数组 for (int i = 1; i <= m; i++) ans[i] = mark[i] ? oo : s; // MST中的边初始为无穷大，非MST边初始为s // 从任意点开始DFS，构建MST的树结构 dfs(1); // 重置并查集 for (int i = 1; i <= n; i++) f[i] = 0; // 处理每条不在MST中的边，计算其作为替换边时的代价 for (int i = 1; i <= m; i++) { if (mark[p[i]]) continue; // 跳过MST中的边 int x = getf(u[p[i]]), y = getf(v[p[i]]); // 沿着树上路径向上跳，直到相遇（LCA思想） while (x != y) { if (dep[x] < dep[y]) x ^= y ^= x ^= y; // 交换x和y，保证x更深 int to = u[pid[x]] ^ v[pid[x]] ^ x; // 父节点 // 更新这条树边被当前非树边替换后的总权重 ans[pid[x]] = s - w[pid[x]] + w[p[i]]; f[x] = to; // 路径压缩 x = getf(x); } } // 输出结果 for (int i = 1; i <= m; i++) printf("%lld\n", ans[i] < oo ? ans[i] : -1); return 0; }

题库

题库

12853.最小生成树

题解大全 共 0 篇

测试用例

题解大全共 0 篇