Problem E: [CSP-S1][程序阅读] 程序阅读10
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：80
Solved：6
Description
|
struct Edge { int u, v, w; }; bool cmp(Edge a, Edge b) { return a.w < b.w; } int kruskal(int n, vector<Edge> edges) { sort(edges.begin(), edges.end(), cmp); init(n); // 并查集初始化 int res = 0, cnt = 0; for (Edge e : edges) if (find(e.u) != find(e.v)) { merge(e.u, e.v); res += e.w; if (++cnt == n-1) break; } return cnt == n-1 ? res : -1; } |
判断题
1. 若图不连通，返回-1。（ ）
2. 边排序是贪心选择的关键。（ ）
3. `cnt`统计的是边数而非顶点数。（ ）
4. 若存在重边，算法可能选择多条同权边。（ ）
5. 时间复杂度为O(E log E)。（ ）
选择题
6. 对于树`1-2-3`（边权1,2），返回值是：
A. 1 B. 2 C. 3 D. -1
7. 若所有边权相同，MST的边权总和是：
A. (n-1)*w B. n*w C. E*w D. 无法确定
8. 若`edges`为空且n>1，返回值是：
A. 0 B. -1 C. 1 D. 未定义
9. 若`merge`中未按秩合并，可能导致：
A. 错误结果 B. 时间复杂度退化 C. 无法处理重边 D. 无影响
10. 判断MST是否唯一需检查：
A. 是否存在相同权值的边 B. 是否存在割边
C. 是否存在环 D. 无法判断