usaco-2.4.4 牛的旅行

GitHub跳转原题关系图返回列表

Floyd 一次算出各牧场内全源最短路，得每点偏心距与牧场直径；枚举跨牧场点对，新直径取 max(两边偏心距+欧氏新边, 原直径较大者) 的最小值。

OJ: roj

题目 ID: 2038

难度:普及

标签:图论最短路Floyd连通块

创建: 2026-10-01 04:30

更新: 2026-10-07 13:50

前置题目
luogu P1529[USACO2.4] 回家 Bessie Come HomeB 的第 1 步「用 INF 哨兵建距离矩阵、对全图跑一遍 Floyd 得到全源最短路」就是 A 教的「点少就建距离矩阵、一趟 Floyd 出任意两点最短路」这一步，B 只是在其上叠加偏心距/直径、连通块染色与枚举跨块点对；A 是纯 Floyd 模板题、B 难在后续直径流程，属台阶式前置。roj 1342【例4-1】最短路径问题B 的第 1 步直接复用 A 教的「坐标建带权无向邻接矩阵后 Floyd 三重松弛求全源最短路」，只是把结果的用途从查 d(s,t) 换成算偏心距与直径，再叠加连通块染色与跨块点对枚举。

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

农民 John 有 NN（1≤N≤1501\le N\le150）个坐标互不相同的牧区，给定对称 0/1 邻接矩阵，值为 1 的两点间有边、边权为欧几里得距离。边把牧区分成若干连通块（牧场），题目保证至少两个；牧场直径是块内最远两点的最短路长度。恰好在两个不同牧场中各选一个牧区连一条边，使连通后的新牧场直径最小，输出保留 6 位小数。输入第一行为 NN，随后 NN 行坐标、NN 行邻接矩阵。

样例输入：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：块内得到全源最短路，块间保持无穷；据此求每点偏心距（到本块内最远点的距离）与各牧场直径。枚举跨牧场点对 (a,b)(a,b)，新边权取欧氏距离（不是块间为无穷的 d[a][b]d[a][b]），新直径 =min⁡a,bmax⁡(两个原牧场直径, ea+∣ab∣+eb)=\min_{a,b}\max(\text{两个原牧场直径},\,e_a+|ab|+e_b)。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 04:30
# update_at: 2026-10-01 04:33

import sys
from math import dist

INF = float("inf")  # 同一牧场内没有边直接相连的点对，Floyd 开始前的距离哨兵


def floyd(d: list[list[float]], n: int) -> None:
    """在原地把每个连通块内部的最短路算全（块间距离保持 INF）。"""
    for k in range(n):
        dk = d[k]
        for i in range(n):
            di = d[i]
            dik = di[k]
            if dik == INF:  # i 与 k 不同块，k 作中转点帮不到 i
                continue
            for j in range(n):
                via_k = dik + dk[j]
                if via_k < di[j]:
                    di[j] = via_k


def components(adj: list[list[int]], n: int) -> list[int]:
    """给每个牧区染上所在牧场的编号（取块内最小点标号）。"""
    comp = [-1] * n
    for s in range(n):
        if comp[s] != -1:
            continue
        cid = comp[s] = s
        stack = [s]
        while stack:
            for v, ok in enumerate(adj[stack.pop()]):
                if ok and comp[v] == -1:
                    comp[v] = cid
                    stack.append(v)
    return comp


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    pt = [(int(next(data)), int(next(data))) for _ in range(n)]  # 每个牧区的坐标
    # 数据里矩阵行可能带 \r 或行内空格，先全部拼成 0/1 串再按行切块
    cells = b"".join(data).decode()
    adj = [[int(cells[i * n + j]) for j in range(n)] for i in range(n)]  # 邻接矩阵

    # 有边 → 欧几里得边权，无边 → INF，对角线为 0
    d = [[0.0 if i == j else (dist(pt[i], pt[j]) if adj[i][j] else INF)
          for j in range(n)] for i in range(n)]
    floyd(d, n)

    ecc = [max(w for w in d[i] if w != INF) for i in range(n)]  # 每点到本块内最远点的距离

    comp = components(adj, n)  # comp[i] = 牧场编号
    dia = [max(ecc[i] for i in range(n) if comp[i] == c) for c in set(comp)]  # 每个牧场的直径

    # 新直径 = 前半段最长路 + 新边 + 后半段最长路；新边权是两点间的欧几里得距离
    ans = min(ecc[i] + ecc[j] + dist(pt[i], pt[j])
              for i in range(n) for j in range(n) if comp[i] != comp[j])
    # 连新边不会把某个牧场自身"压细"，答案不低于原牧场直径的较大者
    print(f"{max(ans, max(dia)):.6f}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:01
 * update_at: 2026-10-06 10:01
 */
#include <cmath>
#include <cstdio>

typedef long long ll;

const int MAXN = 155;
const double INF = 1e18; // 距离哨兵：表示两点当前不连通

int n;                   // 牧区数量
ll px[MAXN], py[MAXN];   // 每个牧区的坐标
bool linked[MAXN][MAXN]; // 原图邻接矩阵，1 表示两点直接相连
double dis[MAXN][MAXN];  // dis[i][j] Floyd 后为块内最短路，不连通时仍为 INF
int comp[MAXN];          // comp[i] = 牧区 i 所在牧场的编号（取块内最小编号）
double ecc[MAXN];        // ecc[i] = 牧区 i 到本块内最远点的距离
double diam[MAXN];       // diam[c] = 编号为 c 的牧场的直径

// 两个牧区之间的欧几里得距离。
double euclid(int a, int b) {
    double dx = px[a] - px[b];
    double dy = py[a] - py[b];
    return sqrt(dx * dx + dy * dy);
}

// 全图跑一遍 Floyd：块内得到全源最短路，块间距离保持 INF。
void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dis[i][k] >= INF) continue; // i 与 k 不连通，k 不能作中转点
            for (int j = 0; j < n; j++) {
                double via = dis[i][k] + dis[k][j];
                if (via < dis[i][j]) dis[i][j] = via;
            }
        }
    }
}

int stk[MAXN]; // 连通块染色用的手写栈

// 给每个牧区染上所在牧场的编号，块内最小点标号作为该块编号。
void find_components() {
    for (int i = 0; i < n; i++) comp[i] = -1;
    for (int s = 0; s < n; s++) {
        if (comp[s] != -1) continue;
        comp[s] = s;
        int top = 0;
        stk[top++] = s;
        while (top > 0) {
            int u = stk[--top];
            for (int v = 0; v < n; v++) {
                if (linked[u][v] && comp[v] == -1) {
                    comp[v] = s;
                    stk[top++] = v;
                }
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &px[i], &py[i]);
    }

    // 矩阵行可能带行内空格或 CRLF 行尾：把所有剩余 token 拼成 0/1 串，再按每行 n 个切开。
    char cells[MAXN * MAXN + 10];
    char token[MAXN * MAXN + 10];
    int len = 0;
    while (scanf("%s", token) == 1) {
        for (int t = 0; token[t] != '\0'; t++) {
            if (len < MAXN * MAXN) cells[len++] = token[t];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            linked[i][j] = (cells[i * n + j] == '1');
        }
    }

    // 初始距离矩阵：对角线 0，有边用欧氏距离，无边用 INF。
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dis[i][j] = 0;
            else if (linked[i][j]) dis[i][j] = euclid(i, j);
            else dis[i][j] = INF;
        }
    }

    floyd();

    // 偏心距：每个点到本块内最远点的距离。
    for (int i = 0; i < n; i++) {
        double best = 0;
        for (int j = 0; j < n; j++) {
            if (dis[i][j] < INF && dis[i][j] > best) best = dis[i][j];
        }
        ecc[i] = best;
    }

    find_components();

    // 每个牧场的直径 = 块内偏心距的最大值。
    for (int i = 0; i < n; i++) diam[i] = 0;
    for (int i = 0; i < n; i++) {
        if (ecc[i] > diam[comp[i]]) diam[comp[i]] = ecc[i];
    }

    // 枚举跨牧场点对 (i, j)：新边权是两点间欧氏距离（不是 dis[i][j]，跨块时它是 INF）。
    double best_link = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (comp[i] == comp[j]) continue;
            double cand = ecc[i] + euclid(i, j) + ecc[j];
            if (cand < best_link) best_link = cand;
        }
    }

    // 新直径还要与原有各牧场直径取 max：连边只增不减，两个“团块”型牧场不会被压细。
    double ans = best_link;
    for (int i = 0; i < n; i++) {
        if (comp[i] == i && diam[i] > ans) ans = diam[i];
    }

    printf("%.6f\n", ans);
    return 0;
}