GESP-C++八级 题库
共 30 道题
,第 2 / 2 页
· 按题型筛选,点「查看答案」核对解析
21
单选题
适中
下面Floyd算法中,横线处应该填入的是( )。
A
map[i][j] < map[i][k] + map[k][j]
B
map[i][j] > map[i][k] + map[k][j]
C
map[i][j] > map[i][k] - map[k][j]
D
map[i][j] < map[i][k] - map[k][j]
答案与解析
正确答案:B
Floyd算法本质是个DP,或者可以理解为松弛操作:
i和j的最短路如果可以通过中间节点k做更新:
则需要map[i][j]>map[i][k]+map[k][j];选B。
22
单选题
适中
一个无向图包含 n 个顶点,则其最小生成树包含多少条边?( )。
A
n-1
B
n
C
n+1
D
最小生成树可能不存在。
答案与解析
正确答案:D
这道题暂未补解析。
25
判断题
偏易
使用 math.h 或 cmath 头文件中的函数,对于 int 类型的变量 x ,表达式 fabs(x) 和 sqrt(x * x) 的结果总是近似相等的。
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
28
判断题
偏易
已知两个 double 类型的变量 r 和 theta 分别表示一个扇形的圆半径及圆心角(弧度),则扇形的周长可以通过表达式 (2 + theta) * r 求得。
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
29
判断题
偏易
从32名学生中选出2人分别担任男生班长和女生班长(男生班长必须是男生,女生班长必须是女生),则共有C(32,3)/2种不同的选法。
A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
30
简答题
偏难
最小生成树



答案与解析
参考答案
#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;
}