蓝桥杯2024年第十五届省赛真题-狡兔 k 窟

### 蓝桥杯2024第十五届省赛真题 '狡兔 k 窟' 题目详情 题目描述涉及一个兔子试图通过构建多个洞穴来躲避猎人的追捕。具体来说，有 n 个节点表示不同位置的洞穴，m 条边连接这些节点形成无向图结构。每条边上有一个权值 w 表示两个洞穴之间的距离。为了增加逃脱的成功率，兔子希望找到一种方法使得从任意一个起点出发到达其他任何终点的过程中所经过的最大单次跳跃不超过某个限定值 K。 #### 输入格式 输入的第一行为三个整数 n (1 ≤ n ≤ 10^5)， m (n−1≤m≤min(10^5,n(n−1)/2)) 和 k (1 ≤ k ≤ 10^9)，分别代表洞穴的数量、路径数量以及允许的最大跳跃长度。 接下来 m 行，每一行包含三个整数 u,v,w (1 ≤u ,v ≤ n ; 0<w<∞ ) ，表示存在一条由 u 至 v 的双向道路，其长度为 w 。保证给出的数据构成连通图。 #### 输出格式 输出仅一行，即满足条件下的最少需要挖掘的新洞穴数目 s （初始情况下假设有足够的旧洞穴供使用）。如果没有必要新建，则输出 0 。 --- ### 解决方案概述 该问题可以转化为最小生成树(MST)加上额外处理的问题。首先利用 Kruskal 或 Prim 算法求得原图中的 MST，在此基础上考虑如何调整以适应最大跳远限制的要求： - 对于所有不在当前MST内的边 e=(a,b)，当且仅当加入这条边后不会违反已有的最长边约束时才将其纳入考量范围； - 如果某时刻发现无法继续扩展而仍有未访问过的顶点，则说明必须新增至少一个新的中心点作为桥梁连接剩余部分； - 记录下每次因为上述原因被迫创建新结点的情况直至整个网络完全联通为止。 最终返回所需添加的总节点数即可得到正确答案[^1]。 ```python from typing import List, Tuple import heapq def minimum_extra_holes( num_nodes: int, edges: List[Tuple[int, int, int]], max_jump_length: int ) -> int: parent = list(range(num_nodes)) def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): rootX = find(x) rootY = find(y) if rootX != rootY: parent[rootX] = rootY sorted_edges = sorted(edges, key=lambda edge: edge[2]) extra_holes_needed = 0 used_edge_count = 0 last_used_weight = 0 for node_a, node_b, weight in sorted_edges: if used_edge_count >= num_nodes - 1 + extra_holes_needed or \ weight > max_jump_length * 2 ** extra_holes_needed: break if find(node_a) != find(node_b): union(node_a, node_b) last_used_weight = weight used_edge_count += 1 if last_used_weight == max_jump_length and\ used_edge_count < num_nodes - 1 + extra_holes_needed: extra_holes_needed += 1 remaining_components = sum([find(v)==v for v in range(num_nodes)]) total_extra_holes = extra_holes_needed + remaining_components - 1 return total_extra_holes if total_extra_holes >= 0 else 0 ```