【Floyd算法】牛的旅行

题目

1125. 牛的旅行 - AcWing题库

农民John的农场里有很多牧区，有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言，你能看到至少有两个牧区不连通。

现在，John想在农场里添加一条路径（注意，恰好一条）。

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

考虑如下的两个牧场，每一个牧区都有自己的坐标：

图 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 \le N \le 150$ ,
$0 \le X,Y \le 10^5$

输入样例：

输出样例：

22.071068

解题

方法一：Floyd算法

思路

题目要求：给定多个连通块，选两个不同的连通块，在两块中各取一点进行连接以合成一个连通块，并使 合并后 的 所有连通块 中的最大直径^[1] 尽可能小（以下简称为 $ans$ ），求这个 $ans$ 。

题目中提到 两节点之间距离都是最短距离 ，故我们必然会在之后枚举点到点之间到距离，再加上本题的数据范围只有 $1 \le N \le 150$ ，所以首先用 Floyd 算法求出任意两点之间的距离 $dists$ （ $dists[i][j]$ 表示顶点 $i, j$ 之间的最短距离）。

由于 新加边所连接的两个节点 必须在 两个不同的连通块之间 ，所以该边不会对这两个 连通块内 的顶点距离有影响，那么 $ans$ 至少也应该是合并前所有连通块直径的最大值。

对于任意一个顶点 $i$ ，其距离 与其同连通块中的最远顶点 的最短距离记为 $maxd[i]$ 。那么根据连通块直径的定义^[1:1] ，所有连通块的直径的集合一定是 $maxd$ 的子集，那么就有 $ans > \max(maxd)$ 。

尝试在图中分别枚举两个顶点 $i, j$ ，若 $i, j$ 不在同一个连通块中就尝试连接它们，此时 必须通过新边 的 $i, j$ 之间的距离就为 $nd = maxd[i] + i 与 j在坐标上的距离 + maxd[j]$ ，但是 $nd$ 不一定是这个合成起来的新连通块的直径 ，所以不能简单地对所有 $nd$ 取最小，还要保证 $ans > \max(maxd)$ 。

最终： $ans = \max(\max(maxd), \min(nd))$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    static double INF = 1e9;
    static int n;
    static double[][] poses, dists;
    
    static double getDist(double[] u, double[] v) {
        return Math.sqrt(Math.pow(u[0] - v[0], 2) + Math.pow(u[1] - v[1], 2));
    }
    
    static void floyd() {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    dists[i][j] = Math.min(dists[i][j], dists[i][k] + dists[j][k]);
                }
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        n = (int) in.nval;
        poses = new double[n + 1][2];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            poses[i][0] = in.nval;
            in.nextToken();
            poses[i][1] = in.nval;
        }
        dists = new double[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            char[] s = ('\0' + br.readLine()).toCharArray();
            for (int j = 1; j <= n; ++j) {
                if (i == j) continue;
                char c = s[j];
                dists[i][j] = c == '0' ? INF : getDist(poses[i], poses[j]);
            }
        }
        floyd();
        double res1 = 0.0;
        double[] maxd = new double[n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dists[i][j] > INF / 2) continue;
                maxd[i] = Math.max(maxd[i], dists[i][j]);
            }
            res1 = Math.max(res1, maxd[i]);
        }
        double res2 = INF;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dists[i][j] > INF / 2) {
                    res2 = Math.min(res2, maxd[i] + getDist(poses[i], poses[j]) + maxd[j]);
                }
            }
        }
        System.out.printf("%.6f\n", Math.max(res1, res2));
    }
}

一个连通块的直径指的是在连通块内任取两顶点，能得到的 最大的 「两点之间的 最短距离 」。 ↩︎ ↩︎

目录CONTENT

【Floyd算法】牛的旅行

题目

解题

方法一：Floyd算法

思路

代码

评论区