```markdown ### 代码概述 本 Python 代码实现与 C++ 版完全一致的算法逻辑：在树状酒店网络中，枚举所有大小为 $M$ 的食材子集（位掩码），对每个子集计算被直接满足的酒店集合；再通过**二分答案 + 暴力覆盖判定**，求出使所有未满足酒店到最近满足酒店的**最大距离最小化**的最优值。针对 $N \le 100$、$K \le 10$ 的约束，时间可接受。 --- ### 代码解析 ```python import sys from collections import deque def main(): data = sys.stdin.read().split() it = iter(data) N = int(next(it)); M = int(next(it)); K = int(next(it)) # 读取 N 行需求矩阵 (N x K) need = [] for _ in range(N): row = [int(next(it)) for _ in range(K)] need.append(row) # 建树（邻接表），0-indexed tree = [[] for _ in range(N)] for _ in range(N - 1): u = int(next(it)) - 1; v = int(next(it)) - 1; w = int(next(it)) tree[u].append((v, w)) tree[v].append((u, w)) # BFS 预处理全源最短距离 dist[i][j] def bfs(start): dist_from_start = [-1] * N q = deque([start]) dist_from_start[start] = 0 while q: u = q.popleft() for v, w in tree[u]: if dist_from_start[v] == -1: dist_from_start[v] = dist_from_start[u] + w q.append(v) return dist_from_start dist = [bfs(i) for i in range(N)] # dist[i][j] = 酒店 i 到 j 的距离 # 枚举所有含 M 个食材的子集（位掩码） ans = float('inf') total_masks = 1 << K for mask in range(total_masks): if bin(mask).count('1') != M: continue # 计算该 mask 下哪些酒店被直接满足 satisfied = [True] * N for i in range(N): for j in range(K): if need[i][j] and not (mask & (1 << j)): satisfied[i] = False break # 二分查找最小可行最大距离 T lo, hi = 0, 10**8 best_T = hi while lo <= hi: mid = (lo + hi) // 2 # 检查：每个 unsatisfied 酒店是否能在距离 <= mid 内到达某个 satisfied 酒店？ valid = True for i in range(N): if satisfied[i]: continue covered = False for j in range(N): if satisfied[j] and dist[i][j] <= mid: covered = True break if not covered: valid = False break if valid: best_T = mid hi = mid - 1 else: lo = mid + 1 ans = min(ans, best_T) print(ans) if __name__ == '__main__': main() ``` **关键说明**： - 使用 `bfs()` 替代 DFS（更符合 Python 习惯且避免递归深度问题），共运行 $N$ 次，每次 $O(N)$，总预处理 $O(N^2)$； - `bin(mask).count('1')` 等效于 `__builtin_popcount`，判断是否选中 $M$ 种食材； - 覆盖判定采用朴素 $O(N^2)$ 双重循环（因 $N \le 100$，最坏 $10^4$ 次/次二分，可接受）； - 二分上界设为 $10^8$（远大于最大可能距离 $10^6 \times 100 = 10^8$），安全覆盖； - 输入使用 `sys.stdin.read().split()` 加速，适配大输入。 --- ### 知识点 - **树上多源 BFS 距离预处理**：对每个节点做一次 BFS，得全源距离矩阵，$O(N(N+E)) = O(N^2)$。 - **位掩码子集枚举**：用整数 `mask` 表示食材选择状态，`bin(mask).count('1')` 快速统计选中数。 - **二分答案可行性检验**：将最小化最大值问题转化为单调判定问题，降低优化复杂度。 ```