[USACO2.4] 牛的旅行 Cow Tours

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

先 Floyd 求每个连通块内任意两点最短路，再枚举跨块连边，用两端点到各自块内最远点的距离更新合并后的最小直径。

OJ: luogu

题目 ID: P1522

难度:普及+/提高

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

日期: 2026-06-20 04:25

题意

给你 n 个牧区的坐标，以及一张 0/1 邻接矩阵。

1 表示这两个牧区之间本来就有路
路长等于这两个点的欧几里得距离
一个连通块就是一个牧场

现在必须在两个不同连通块之间新建一条路，要求新图中“各个连通块的直径最大值”尽量小，输出这个最小值。

这里的直径不是直线距离，而是：

同一个连通块里，两点之间最短路的最大值

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115#include <bits/stdc++.h>
using namespace std;

const int MAXN = 155;
const long double INF = 1e100L;

int n;
long double x[MAXN], y[MAXN];
long double base_dist[MAXN][MAXN];
long double work_dist[MAXN][MAXN];

long double get_dist(int i, int j) {
    long double dx = x[i] - x[j];
    long double dy = y[i] - y[j];
    return sqrtl(dx * dx + dy * dy);
}

void floyd(long double dist_arr[MAXN][MAXN]) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist_arr[i][k] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= n; j++) {
                if (dist_arr[k][j] >= INF / 2) {
                    continue;
                }
                long double nd = dist_arr[i][k] + dist_arr[k][j];
                if (nd < dist_arr[i][j]) {
                    dist_arr[i][j] = nd;
                }
            }
        }
    }
}

long double calc_diameter(long double dist_arr[MAXN][MAXN]) {
    long double ret = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist_arr[i][j] >= INF / 2) {
                continue;
            }
            if (dist_arr[i][j] > ret) {
                ret = dist_arr[i][j];
            }
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                base_dist[i][j] = 0;
            }
            else {
                base_dist[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            if (s[j - 1] == '1') {
                base_dist[i][j] = get_dist(i, j);
            }
        }
    }

    floyd(base_dist);

    long double answer = INF;

    // 朴素思路：枚举每一条可加的新边，真的把它加上，再重跑一次 Floyd。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (base_dist[i][j] < INF / 2) {
                continue;
            }

            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    work_dist[a][b] = base_dist[a][b];
                }
            }

            long double bridge = get_dist(i, j);
            work_dist[i][j] = bridge;
            work_dist[j][i] = bridge;

            floyd(work_dist);

            long double cand = calc_diameter(work_dist);
            if (cand < answer) {
                answer = cand;
            }
        }
    }

    cout << fixed << setprecision(6) << (double) answer << '\n';

    return 0;
}

这个暴力的做法很直接：

先求出原图的最短路
枚举一条原本不连通的点对 (i,j) 作为新边
真的把这条边加进去
再跑一次 Floyd
统计加边后的最大有限最短路，也就是当前答案

这样写完全贴着题意走，但如果每条候选新边都重跑一次 Floyd，代价就太大了。

关键观察是：
如果把 i 和 j 连起来，那么新直径只可能来自三部分里的最大值：

原来某个连通块自己的直径
i 所在连通块里的某个点走到 i
经过新边，再从 j 走到它所在连通块里的某个点

也就是说，真正需要关心的是：

farthest[i]：点 i 到自己连通块内最远点的最短路长度

那么若新边连的是 (i,j)，跨过这条新边形成的最长路长度就是：

farthest[i] + dist(i,j) + farthest[j]

下面这张图展示的就是这个结构：

graph LR
  A["块 1 中离 i 最远的点"] --- I["端点 i"]
  I -. "新边 dist(i,j)" .- J["端点 j"]
  J --- B["块 2 中离 j 最远的点"]

图里真正要看的不是具体边数，而是“新边左右两侧各接上一段块内最远路”。
所以只要先知道每个点在原连通块里的最远距离，就能立刻算出这条新边可能造成的最长跨块路径。
再和原有各个连通块的直径取最大值，就是连这条边后的总直径。

于是正式做法就是：

先 Floyd，求出原图任意两点最短路
对每个点 i，统计 farthest[i]
顺便求出原图所有连通块里的最大直径 old_diameter
枚举所有原本不连通的点对 (i,j)
计算候选值：
- max(old_diameter, farthest[i] + dist(i,j) + farthest[j])
取最小值

和代码的对应关系也很清楚：

dist_arr：Floyd 后的最短路矩阵
farthest_dist[i]：点 i 到本块最远点的距离
old_diameter：原图所有连通块里的最大直径
双重循环枚举原本不连通的 (i,j)，更新答案

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105#include <bits/stdc++.h>
using namespace std;

const int MAXN = 155;
const long double INF = 1e100L;

int n;
long double x[MAXN], y[MAXN];
long double dist_arr[MAXN][MAXN];
long double farthest_dist[MAXN];

long double get_dist(int i, int j) {
    long double dx = x[i] - x[j];
    long double dy = y[i] - y[j];
    return sqrtl(dx * dx + dy * dy);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; j++) {
            if (s[j - 1] == '1') {
                dist_arr[i][j] = get_dist(i, j);
            }
        }
    }

    // 先求出原图中每个连通块内部的任意两点最短路。
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist_arr[i][k] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= n; j++) {
                if (dist_arr[k][j] >= INF / 2) {
                    continue;
                }
                long double nd = dist_arr[i][k] + dist_arr[k][j];
                if (nd < dist_arr[i][j]) {
                    dist_arr[i][j] = nd;
                }
            }
        }
    }

    long double old_diameter = 0;
    for (int i = 1; i <= n; i++) {
        farthest_dist[i] = 0;
        for (int j = 1; j <= n; j++) {
            if (dist_arr[i][j] >= INF / 2) {
                continue;
            }
            if (dist_arr[i][j] > farthest_dist[i]) {
                farthest_dist[i] = dist_arr[i][j];
            }
        }
        if (farthest_dist[i] > old_diameter) {
            old_diameter = farthest_dist[i];
        }
    }

    long double answer = INF;

    // 枚举新边的两个端点。只有原本不连通时，这条边才有意义。
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (dist_arr[i][j] < INF / 2) {
                continue;
            }

            long double bridge = get_dist(i, j);
            long double new_diameter = farthest_dist[i] + bridge + farthest_dist[j];

            // 别的连通块可能还有更大的旧直径，也要一起保留。
            long double cand = max(old_diameter, new_diameter);
            if (cand < answer) {
                answer = cand;
            }
        }
    }

    cout << fixed << setprecision(6) << (double) answer << '\n';

    return 0;
}

复杂度

Floyd 的时间复杂度是 $O(n^3)$ 。

后面统计 farthest 和枚举新边都是 $O(n^2)$ 。

所以总时间复杂度是：

$O(n^3)$

空间复杂度是：

$O(n^2)$

总结

这题最容易卡住的地方，是以为“每试一条新边都要重新跑最短路”。

其实 Floyd 只需要对原图跑一次。
之后每个点到本块最远点的距离已经固定了。
枚举新边 (i,j) 时，新增的影响只会体现在：

farthest[i] + dist(i,j) + farthest[j]

把这个式子想明白，这题就从“反复重算最短路”变成了“Floyd + 枚举连边”的标准模型。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1522 [USACO2.4] 牛的旅行 Cow Tours

题目描述

Farmer John 的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区 称为一个牧场。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John 就有多个牧场了。

John 想在牧场里添加恰好一条路径。对这条路径有以下限制：

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是 最短的距离）。考虑如下的有 5 个牧区的牧场，牧区用 * 表示，路径用直线表示。每一个牧区都有自己的坐标：

plain

1
2
3
4
5
6
7
8
9
10                (15,15) (20,15)
                 D       E
                 *-------*
                 |     _/|
                 |   _/  |
                 | _/    |
                 |/      |
        *--------*-------*
        A        B       C
     (10,10)  (15,10) (20,10)

这个牧场的直径大约是 $12.07106$ ，最远的两个牧区是 A 和 E，它们之间的最短路径是 $A \to B \to E$ 。

这里是 John 的另一个牧场：

plain

1
2
3
4
5
6
7
8                         *F(30,15)
                        / 
                      _/  
                    _/    
                   /      
                  *------* 
                  G      H
                  (25,10)   (30,10)

在这个例子中，他刚好有这两个牧场。John 将会在这两个牧场中各选一个牧区（即从 $\{A,B,C,D,E\}$ 中选择一个牧区，从 $\{F,G,H\}$ 中选择一个牧区），然后用一条路径将它们连起来，使得连通后这个新的更大的牧场的直径尽可能小。

注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：

plain

1
2
3
4
5
6
7
8
9　 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

其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。

输入文件至少包括两个不连通的牧区。

请编程找出一条连接属于两个 不同牧场 的牧区的路径，使得连上这条路径后，这个更大的新牧场的直径尽可能小。输出在所有合法的连接方案中，新牧场直径的最小值。

输入格式

第一行一个整数 $N$ （ $1 \leq N \leq 150$ ），表示牧区数。

接下来 $N$ 行，每行两个整数 $X,Y$ （ $0 \leq X ,Y \leq 10^5$ ），表示 $N$ 个牧区的坐标。注意每个牧区的坐标都是不一样的。

接下来 $N$ 行，每行 $N$ 个数字，代表邻接矩阵 $M$ 。第 $i$ 行第 $j$ 列的数字为 $1$ ，表示 $i$ 号牧区和 $j$ 号牧区之间存在一条道路直接相连；第 $i$ 行第 $j$ 列的数字为 $0$ ，表示 $i$ 号牧区和 $j$ 号牧区之间不存在直接相连的道路。

保证 $M_{i,j} = M_{j,i}$ 。

输出格式

只有一行，包括一个实数，表示所求直径。数字保留六位小数，末位四舍五入。

输入输出样例 #1

输入 #1

text

输出 #1

text

122.071068

说明/提示

样例对应题目描述中的情况。

最优解是连接 C 牧区和 G 牧区，连接后图上只有一个牧场。这个牧场的直径为 $A \to B \to C \to G \to F$ ，长度约为 $22.071068$ 。可以证明不存在更优的方案。

USACO 2.4

[USACO2.4] 牛的旅行 Cow Tours

目录

题意

思路

代码

复杂度

总结

一图流解析