# Floyd算法实战：如何用Python解决洛谷P1522牛的旅行问题 洛谷P1522是一道经典的图论问题，考察Floyd算法的灵活应用。本文将带你从问题分析到代码实现，完整拆解解题思路，最后给出经过详细注释的Python代码。 ## 1. 问题分析与建模 题目描述：给定N个牧区（顶点）的坐标和连通情况（邻接矩阵），要求通过连接两个不连通的牧区，使得新形成的牧场直径最小。牧场直径定义为牧场中任意两点间最短路径的最大值。 **关键建模步骤：** 1. 将牧区抽象为图中的顶点 2. 牧区间的连通关系构成边，边权为两点间欧氏距离 3. 牧场对应图中的连通分量 4. 牧场直径即连通分量内所有顶点对最短路径的最大值 ```python import math def calc_distance(p1, p2): """计算两点间欧氏距离""" return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) ``` ## 2. Floyd算法核心思想 Floyd算法采用动态规划思想，通过三重循环逐步优化最短路径估计： 1. 初始化距离矩阵：直接相连的点赋值为边权，不相连的赋值为无穷大 2. 三重循环更新：对于每个中间点k，检查是否通过k能缩短i到j的距离 **算法复杂度分析：** - 时间复杂度：O(N³) - 空间复杂度：O(N²) ```python def floyd(n, dist): """Floyd算法实现""" for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] ``` ## 3. 邻接矩阵的特殊处理 题目给出的邻接矩阵需要特殊处理： 1. '0'表示不连通，'1'表示连通 2. 对于连通的点对，边权为实际欧氏距离 3. 对于不连通的点对，初始距离设为无穷大(INF) ```python INF = float('inf') def build_distance_matrix(points, adj): """构建初始距离矩阵""" n = len(points) dist = [[INF]*n for _ in range(n)] for i in range(n): dist[i][i] = 0 # 对角线设为0 for j in range(n): if adj[i][j] == '1': dist[i][j] = calc_distance(points[i], points[j]) return dist ``` ## 4. 连通分量直径计算优化 计算每个连通分量的直径（即内部最远点对距离）时，可以采用以下优化： 1. 先计算每个点到同连通分量内其他点的最远距离 2. 连通分量的直径即为这些最远距离中的最大值 ```python def compute_component_diameters(n, dist, components): """计算各连通分量的直径""" diameters = [0] * len(components) for comp_idx, comp in enumerate(components): max_dist = 0 for i in comp: for j in comp: if dist[i][j] > max_dist: max_dist = dist[i][j] diameters[comp_idx] = max_dist return diameters ``` ## 5. 完整解题思路与实现 综合以上步骤，完整解题流程如下： 1. 输入处理：读取顶点坐标和邻接矩阵 2. 构建初始距离矩阵 3. 运行Floyd算法计算全源最短路径 4. 找出所有连通分量 5. 计算各连通分量直径 6. 枚举所有可能的连接方案，计算新直径 7. 找出所有新直径中的最小值 **完整AC代码：** ```python import math from collections import defaultdict def main(): # 输入处理 n = int(input()) points = [] for _ in range(n): x, y = map(int, input().split()) points.append((x, y)) adj = [input().strip() for _ in range(n)] # 构建初始距离矩阵 INF = float('inf') dist = [[INF]*n for _ in range(n)] for i in range(n): dist[i][i] = 0 for j in range(n): if adj[i][j] == '1': dist[i][j] = math.sqrt((points[i][0]-points[j][0])**2 + (points[i][1]-points[j][1])**2) # Floyd算法计算全源最短路径 for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] # 找出所有连通分量 visited = [False] * n components = [] for i in range(n): if not visited[i]: queue = [i] visited[i] = True component = [] while queue: u = queue.pop() component.append(u) for v in range(n): if not visited[v] and dist[u][v] < INF: visited[v] = True queue.append(v) components.append(component) # 计算各连通分量直径 diameters = [0] * len(components) max_in_component = [0] * n # 每个点在所属连通分量中的最远距离 for comp_idx, comp in enumerate(components): current_max = 0 for i in comp: max_dist = 0 for j in comp: if dist[i][j] > max_dist: max_dist = dist[i][j] max_in_component[i] = max_dist if max_dist > current_max: current_max = max_dist diameters[comp_idx] = current_max # 枚举所有可能的连接方案 min_new_diameter = INF # 只需要考虑不同连通分量之间的连接 for i in range(len(components)): for j in range(i+1, len(components)): comp1 = components[i] comp2 = components[j] # 找出两个连通分量中距离相加最小的点对 min_sum = INF for u in comp1: for v in comp2: d = math.sqrt((points[u][0]-points[v][0])**2 + (points[u][1]-points[v][1])**2) if max_in_component[u] + d + max_in_component[v] < min_sum: min_sum = max_in_component[u] + d + max_in_component[v] # 新直径可能来自三部分： # 1. 原连通分量1的直径 # 2. 原连通分量2的直径 # 3. 通过新边的最长路径 new_diameter = max(diameters[i], diameters[j], min_sum) if new_diameter < min_new_diameter: min_new_diameter = new_diameter # 输出结果，保留6位小数 print("{0:.6f}".format(min_new_diameter)) if __name__ == "__main__": main() ``` ## 6. 算法优化与注意事项 1. **连通分量处理优化**：使用并查集可以更高效地找出连通分量 2. **距离计算缓存**：预先计算并缓存所有点对间的欧氏距离 3. **边界情况处理**： - 所有牧区原本就连通的情况 - 只有两个连通分量的情况 4. **浮点数精度**：注意比较浮点数时的精度问题 ```python # 使用并查集优化连通分量查找 class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root != y_root: self.parent[y_root] = x_root # 在构建距离矩阵时初始化并查集 uf = UnionFind(n) for i in range(n): for j in range(n): if adj[i][j] == '1': uf.union(i, j) ``` 通过本文的详细讲解和完整代码实现，你应该能够深入理解Floyd算法在图论问题中的应用，并掌握解决类似问题的通用方法。在实际编程竞赛中，这类问题往往需要综合运用多种算法技巧，关键在于将实际问题准确建模为图论问题，然后选择合适的算法解决。