简答题 偏难
#19971

最小生成树

最小生成树

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 100005; const int M = 200005; const long long INF = 1e18; int n, m; // 存每条边两端点、权值、边编号数组 int u[M], v[M], w[M], p[M]; // 链式前向星:h表头,id存边编号,nx下一条边,et边计数 int h[N], id[M], nx[M], et; // 并查集父数组f,mark标记是否是最小生成树树边 int f[N], mark[M]; long long sum_mst, ans[M]; // dep深度,pid记录到达该点的树边编号 int dep[N], pid[N]; // 按边权从小到大排序 bool cmp(int x, int y) {     return w[x] &lt; w[y]; } // 带路径压缩并查集查找,0代表根节点 int getf(int u) {     if (!f[u]) return u;     return f[u] = getf(f[u]); } // 链式前向星加边:x连接编号为p的边 void link(int x, int edge_id) {     id[++et] = edge_id;     nx[et] = h[x];     h[x] = et; } // DFS遍历最小生成树,求每个点深度、记录到达当前点的树边pid[x] void dfs(int x, int fa = 0, int edge_id = 0) {     dep[x] = dep[fa] + 1;     pid[x] = edge_id;     for (int i = h[x]; i; i = nx[i]) {         // 异或快速求对端:u^v^x 得到另一个端点         int to = u[id[i]] ^ v[id[i]] ^ x;         if (to != fa) {             dfs(to, x, id[i]);         }     } } int main() {     scanf("%d%d", &amp;n, &amp;m);     // 读入所有边     for (int i = 1; i &lt;= m; ++i) {         scanf("%d%d%d", &amp;u[i], &amp;v[i], &amp;w[i]);         p[i] = i;     }     // Kruskal:边按权升序     sort(p + 1, p + m + 1, cmp);     // 1. Kruskal构建最小生成树     for (int i = 1; i &lt;= m; ++i) {         int eid = p[i];         int x = u[eid], y = v[eid];         int fx = getf(x), fy = getf(y);         if (fx == fy) continue;         // 选为树边,标记并累加MST总权值         mark[eid] = 1;         f[fx] = fy;         sum_mst += w[eid];         // 加入MST链式前向星         link(x, eid);         link(y, eid);     }     // 初始化答案:树边暂设无穷INF,非树边初始答案就是MST总和sum_mst     for (int i = 1; i &lt;= m; ++i) {         ans[i] = mark[i] ? INF : sum_mst;     }     // DFS求MST上每个点深度、对应树边pid     dfs(1);     // 重置并查集,用于按非树边更新树边答案     for (int i = 1; i &lt;= n; ++i) f[i] = 0;     // 2. 遍历所有非树边,更新路径上树边的替换答案     for (int i = 1; i &lt;= m; ++i) {         int eid = p[i];         if (mark[eid]) continue; // 跳过树边,只处理非树边         int x = getf(u[eid]), y = getf(v[eid]);         // 向上爬LCA路径,统一路径上所有树边的答案         while (x != y) {             // 保证x更深             if (dep[x] &lt; dep[y]) swap(x, y);             // pid[x]是连接x与父节点的树边             int tree_edge = pid[x];             // 替换这条树边后的新MST权值             ans[tree_edge] = sum_mst - w[tree_edge] + w[eid];             // 并查集向上合并,下次不再处理这条边             int to = u[tree_edge] ^ v[tree_edge] ^ x;             f[x] = to;             x = getf(x);         }     }     // 输出每条边答案:INF代表无法替换,输出-1;否则输出替换后最小生成树权值     for (int i = 1; i &lt;= m; ++i) {         if (ans[i] &lt; INF) printf("%lld\n", ans[i]);         else printf("-1\n");     }     return 0; }</pre>
这道题暂未补解析。