1125 牛的旅行（floyd算法的基础应用）

古城微笑少年丶 2022-08-28 03:51 9阅读 0赞

**1. 问题描述：**

农民John的农场里有很多牧区，有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径（注意，恰好一条）。一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。考虑如下的两个牧场，每一个牧区都有自己的坐标：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16][]  
图 1 是有 5 个牧区的牧场，牧区用"\*"表示，路径用直线表示。图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。图 2 是另一个牧场。这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。输出这个直径最小可能值。

**输入格式**

第 1 行：一个整数 N, 表示牧区数；第 2 到 N+1 行：每行两个整数 X，Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。第 N+2 行到第 2 \* N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。例如，题目描述中的两个牧场的矩阵描述如下：  
A B C D E F G H  
A 0 1 0 0 0 0 0 0  
B 1 0 1 1 1 0 0 0  
C 0 1 0 0 1 0 0 0  
D 0 1 0 0 1 0 0 0  
E 0 1 1 1 0 0 0 0  
F 0 0 0 0 0 0 1 0  
G 0 0 0 0 0 1 0 1  
H 0 0 0 0 0 0 1 0  
输入数据中至少包括两个不连通的牧区。

**输出格式**

只有一行，包括一个实数，表示所求答案。数字保留六位小数。

**数据范围**

1 ≤ N ≤ 150，  
0 ≤ X，Y ≤ 10 ^ 5

**输入样例：**

8  
10 10  
15 10  
20 10  
15 15  
20 15  
30 15  
25 10  
30 10  
01000000  
10111000  
01001000  
01001000  
01110000  
00000010  
00000101  
00000010

**输出样例：**

22.071068  
来源：[https://www.acwing.com/problem/content/1127/][https_www.acwing.com_problem_content_1127]

**2. 思路分析：**

分析题目可以知道我们需要求解出所有旧牧场的直径与在某两个点之间连一条边之后新牧场的直径，然后在这两部分直径中取一个max，也即分两种情况求解：

*  求解每一个联通的牧区中直径的最大值，也即任意两个点之间最远距离的最小值
 *  求解两个不联通的牧区之间中的两个点连一条边之后新牧场直径的最小值

对于第①种情况，其实还是比较好求解的，使用g来存储两个牧场的矩阵，dis来存储牧区中两点之间的最短距离，maxd存储任意两点之间最远距离的最小值，我们可以枚举矩阵g，计算点与点之间的距离并且存储到dis中，然后使用floyd算法计算任意两点之间的最短距离，使用两层循环枚举并计算当前第i个点到其余点最远距离的最小值存储到maxd中，在枚举的过程中计算未连边时候每一个牧区直径的最大值存储到r1，最后求解第二种情况，使用两层循环枚举任意两点i和j，表示在第i个点与第j个点之间连一条边，连上边之后那么新牧场的直径为r2 = maxd\[i\] + max\[j\] + dist，其中dist表示第i个点与第j个点的欧几里得距离，使用一个函数计算结果即可，最后max(r1，r2)就是结果。

**3. 代码如下：**

import math
    
    
    class Solution:
        # 求解两个点之间的欧几里得距离
        def getdistance(self, x: tuple, y: tuple):
            dx = x[0] - y[0]
            dy = x[1] - y[1]
            return math.sqrt(dx * dx + dy * dy)
    
        def process(self):
            # q用来存储每个牧区的坐标
            q = list()
            n = int(input())
            for i in range(n):
                # 输出每一个牧区的坐标
                x, y = map(int, input().split())
                q.append((x, y))
            INF = 10 ** 20
            # dis用来存储两点之间的最短距离
            dis = [[INF] * n for i in range(n)]
            g = list()
            for i in range(n):
                g.append(input())
            for i in range(n):
                for j in range(n):
                    if i == j:
                        dis[i][j] = 0
                    # 当前两个牧区是有边的
                    elif g[i][j] == "1":
                        # 计算两点之间的距离
                        dis[i][j] = self.getdistance(q[i], q[j])
            # floyd算法求解任意两点之间的最短距离
            for k in range(n):
                for i in range(n):
                    for j in range(n):
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
            # 计算两个点之间的最大距离的最小值, 属于第一种情况, r1存储所有牧区的最大直径
            maxd = [0] * n
            r1 = 0
            for i in range(n):
                for j in range(n):
                    # 两个点必须是联通的所以两点之间的距离必须小于INF
                    if dis[i][j] < INF:
                        maxd[i] = max(maxd[i], dis[i][j])
                r1 = max(r1, maxd[i])
            # 下面计算第二种情况
            r2 = INF
            for i in range(n):
                for j in range(n):
                    # 枚举i和j这两个点连一条边求解属于第二种情况的最小的直径
                    if dis[i][j] >= INF:
                        # i, j两个点之间连一条边
                        r2 = min(r2, maxd[i] + maxd[j] + self.getdistance(q[i], q[j]))
            # 保留6位小数
            return "{:.6f}".format(max(r1, r2))
    
    
    if __name__ == "__main__":
        print(Solution().process())

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/924b384e40ad41b18005cb340749b806.png
[https_www.acwing.com_problem_content_1127]: https://www.acwing.com/problem/content/1127/