历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1125. 牛的旅行原题链接简单

作者：

hongjianMa , 2025-04-03 12:40:39 · 湖北 , 所有人可见 , 阅读 7

牛的旅行题解

题目传送门：AcWing 1127. 牛的旅行

一、题目描述

农民John的农场有很多牧区，有些牧区之间有路径连接。所有连通的牧区组成一个牧场。现在农场中至少有两个不连通的牧场。John想在两个不同的牧场中各选一个牧区，用一条路径连接它们，使得新牧场中直径（牧场中最远两个牧区的距离）尽可能小。

二、题目分析

我们需要解决两个问题：
1. 计算每个牧场的直径（即连通块内最远两点的最短距离）
2. 找到连接两个不同牧场的最佳方式，使得新牧场的直径最小

三、解题思路

使用Floyd算法计算所有点对之间的最短距离
对于每个点，计算它到所在连通块中其他点的最远距离
最终结果有两种可能：
原有两个牧场的直径中的较大值
连接两个牧场后形成的新路径的直径（两个端点的最远距离加上新边的长度）

四、算法讲解

Floyd算法用于计算所有点对之间的最短路径：
1. 初始化距离矩阵，直接相连的点距离为坐标距离，不相连的点距离为INF
2. 三重循环更新最短路径，考虑通过中间点k能否缩短i到j的距离

关键点：
- 计算每个点在其连通块中的最远距离maxd[i]
- 结果取两种情况的最大值：
- 原有牧场的最大直径
- 连接两个牧场后可能形成的最小直径

五、代码实现

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
// #define int long long
const int N = 160;
const double INF = 1e20;
PII p[N];          // 存储每个牧区的坐标
char g[N][N];      // 邻接矩阵，表示牧区之间的连接关系
int n;             // 牧区数量
double dist[N][N], // 存储两点之间的最短距离
    maxd[N];       // 存储每个牧区到同一牧场内其他牧区的最远距离

// 计算两点之间的欧几里得距离
double getDis(PII a, PII b)
{
    int dx = a.x - b.x;
    int dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

void floyd()
{
    // 初始化距离矩阵
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j)
                if (g[i][j] == '1') // 如果i和j直接相连
                    dist[i][j] = getDis(p[i], p[j]);
                else
                    dist[i][j] = INF; // 初始为无穷大

    // Floyd算法核心：动态更新最短路径
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    // 计算每个牧区在其连通块内的最远距离
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dist[i][j] < INF)
                maxd[i] = max(maxd[i], dist[i][j]);

    // 情况1：结果至少是两个原牧场直径的较大值
    double res1 = 0;
    for (int i = 0; i < n; i++)
        res1 = max(res1, maxd[i]);

    // 情况2：连接两个牧场后可能形成的新直径
    double res2 = INF;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dist[i][j] >= INF) // 如果i和j不在同一连通块
                res2 = min(res2, getDis(p[i], p[j]) + maxd[i] + maxd[j]);

    // 最终结果是两种情况中的较大值
    printf("%lf", max(res1, res2));
}

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;
    for (int i = 0; i < n; i++)
        cin >> g[i];
    floyd();
}

signed main()
{
    solve();
    return 0;
}