侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【Floyd算法】牛的旅行

GabrielxD
2023-03-08 / 0 评论 / 0 点赞 / 104 阅读 / 1,645 字
温馨提示:
本文最后更新于 2023-03-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1125. 牛的旅行 - AcWing题库


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

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

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

现在,John想在农场里添加一条路径(注意,恰好一条)。

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

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

1.png

图 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

输入数据中至少包括两个不连通的牧区。

输出格式

只有一行,包括一个实数,表示所求答案。

数字保留六位小数。

数据范围

1N1501 \le N \le 150 ,
0X,Y1050 \le X,Y \le 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

解题

方法一:Floyd算法

思路

题目要求:给定多个连通块,选两个不同的连通块,在两块中 各取 一点进行连接以合成一个连通块,并使 合并后所有连通块 中的最大直径[1] 尽可能小(以下简称为 ansans ),求这个 ansans

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

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

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

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

最终: ans=max(max(maxd),min(nd))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));
    }
}

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

0

评论区