题目背景对应的选择、判断题试题 - GESP 202509 C 八级 - 洛谷有题题目描述给定一张包含 n 个结点 m 条边的带权连通无向图结点依次以 1,2,…,n 编号第 i 条边1≤i≤m连接结点 ui​ 与结点 vi​边权为 wi​。对于每条边请你求出从图中移除该条边后图的最小生成树中所有边的边权和。特别地若移除某条边后图的最小生成树不存在则输出 −1。请注意数据可能存在重边。输入格式第一行两个正整数 n,m分别表示图的结点数与边数。接下来 m 行中的第 i 行1≤i≤m包含三个正整数 ui​,vi​,wi​表示图中连接结点 ui​ 与结点 vi​ 的边边权为 wi​。输出格式输出共 m 行第 i 行1≤i≤m包含一个整数表示移除第 i 条边后图的最小生成树中所有边的边权和。若移除第 i 条边后图的最小生成树不存在则输出 −1。输入输出样例输入 #1复制5 5 1 2 4 2 3 3 3 4 1 2 5 2 3 1 8输出 #1复制14 15 -1 -1 10输入 #2复制6 10 1 2 6 2 3 3 3 1 4 3 4 5 4 5 8 5 6 2 6 4 1 3 2 4 5 4 4 3 3 6输出 #2复制15 16 17 -1 15 17 18 15 15 15说明/提示子任务编号测试点占比nm特殊性质120%≤50≤100-230%≤105≤105nm330%≤500≤2×104-420%≤105≤105-对于所有测试点保证 1≤n≤1051≤m≤1051≤ui​,vi​≤n1≤wi​≤109。代码实现#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; const int LOG 18; const ll INF 1e18; struct Edge { int u, v, id; ll w; bool operator(const Edge o) const { return w o.w; } }; int n, m; vectorEdge edges; vectorvectorpairint,int tree; int parent[MAXN], rnk[MAXN]; int up[LOG][MAXN], depth[MAXN]; ll replace_w[MAXN]; int edge_to_node[MAXN]; int find(int x) { while (parent[x] ! x) { parent[x] parent[parent[x]]; x parent[x]; } return x; } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (rnk[a] rnk[b]) swap(a, b); parent[b] a; if (rnk[a] rnk[b]) rnk[a]; return true; } int lca(int a, int b) { if (depth[a] depth[b]) swap(a, b); int diff depth[a] - depth[b]; for (int k 0; k LOG; k) if (diff (1 k)) a up[k][a]; if (a b) return a; for (int k LOG - 1; k 0; k--) { if (up[k][a] ! up[k][b]) { a up[k][a]; b up[k][b]; } } return up[0][a]; } int jump[MAXN]; int find_jump(int x) { while (jump[x] ! x) { jump[x] jump[jump[x]]; x jump[x]; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; edges.resize(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; edges[i].id i; } vectorEdge sorted_edges edges; sort(sorted_edges.begin(), sorted_edges.end()); for (int i 1; i n; i) parent[i] i, rnk[i] 0; tree.assign(n 1, {}); ll mst_weight 0; vectorbool in_mst(m, false); int cnt 0; for (auto e : sorted_edges) { if (unite(e.u, e.v)) { in_mst[e.id] true; mst_weight e.w; tree[e.u].push_back({e.v, e.id}); tree[e.v].push_back({e.u, e.id}); cnt; if (cnt n - 1) break; } } vectorint parent_edge(n 1, -1); queueint q; q.push(1); vectorbool vis(n 1, false); vis[1] true; depth[1] 0; up[0][1] 1; while (!q.empty()) { int u q.front(); q.pop(); for (auto [v, id] : tree[u]) { if (vis[v]) continue; vis[v] true; depth[v] depth[u] 1; up[0][v] u; parent_edge[v] id; edge_to_node[id] v; q.push(v); } } for (int k 1; k LOG; k) for (int i 1; i n; i) up[k][i] up[k-1][up[k-1][i]]; for (int i 0; i m; i) replace_w[i] INF; for (int i 1; i n; i) jump[i] i; for (auto e : sorted_edges) { if (in_mst[e.id]) continue; int u e.u, v e.v; ll w e.w; int l lca(u, v); int x find_jump(u); while (depth[x] depth[l]) { int eid parent_edge[x]; replace_w[eid] w; jump[x] find_jump(up[0][x]); x find_jump(x); } x find_jump(v); while (depth[x] depth[l]) { int eid parent_edge[x]; replace_w[eid] w; jump[x] find_jump(up[0][x]); x find_jump(x); } } for (int i 0; i m; i) { if (!in_mst[i]) { cout mst_weight \n; } else { if (replace_w[i] INF) { cout -1 \n; } else { cout mst_weight - edges[i].w replace_w[i] \n; } } } return 0; }