首页 › 题库 › GESP编程能力等级认证 › 6.1 最小生成树

GESP-C++八级 题库

共 25 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 6.1 最小生成树 清除
21 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

运算符重载是C++语言静态多态的一种典型体现,而使用C语言则无法实现运算符重载。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
22 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

存在一个简单无向图满足:顶点数为6,边数为8,6个顶点的度数分别为3、3、3、3、2、2。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
23 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

已知两个 double 类型的变量 r 和 theta 分别表示一个扇形的圆半径及圆心角(弧度),则扇形的周长可以通过表达式 (2 + theta) * r 求得。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
24 判断题 偏易 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

从32名学生中选出2人分别担任男生班长和女生班长(男生班长必须是男生,女生班长必须是女生),则共有C(32,3)/2种不同的选法。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
25 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

最小生成树

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
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] < 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", &n, &m);
    // 读入所有边
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        p[i] = i;
    }
    // Kruskal:边按权升序
    sort(p + 1, p + m + 1, cmp);

    // 1. Kruskal构建最小生成树
    for (int i = 1; i <= 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 <= m; ++i) {
        ans[i] = mark[i] ? INF : sum_mst;
    }

    // DFS求MST上每个点深度、对应树边pid
    dfs(1);

    // 重置并查集,用于按非树边更新树边答案
    for (int i = 1; i <= n; ++i) f[i] = 0;

    // 2. 遍历所有非树边,更新路径上树边的替换答案
    for (int i = 1; i <= 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] < 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 <= m; ++i) {
        if (ans[i] < INF) printf("%lld\n", ans[i]);
        else printf("-1\n");
    }
    return 0;
}
题目详情