题解 P1522 【牛的旅行 Cow Tours】
heidoudou
2018-09-05 12:52:19
这一题非常之绕。首先需要弄清楚以下几个概念：
1. 牧区： 对应一个点。
2. 牧区之间的距离：实际上是两点之间的 **最短路**。 不要理解成欧几里得距离。只有 **直接连接** 的时候，才可以计算欧几里得距离。
3. 牧场： 一个连通块。
4. 牧场直径： 一个牧场的直径是这个牧场所有的牧区（点）之间 **距离** 的最大值。 说的绕一点就是 **最短路**的最大值。
5. 使用一条边连接两个牧场，使得合成的一个新的牧场的直径最小。意思是加入一条边之后，使得新的牧场的所有点对之间 **最短路** 的最大值 最小。
这道题的正解思路是：
1. 使用 DFS 对连通块染色标记：区分牧场。$O(V + E) = O(n^2)$
2. 使用 Floyd-Warshall 算法计算所有点对之间的 **最短路**。 $O(n^3)$
3. 计算每个牧场中，每个牧区点到其他点的 **最短路** 的最大值。（后面加边的时候要用）
4. 计算每个牧场中，所有最短路的最大值，即每个牧场的直径。 这个可以与 3 一起计算。 $O(n^2)$
5. 最后是找答案：对任意两个点，先判断是否同一个牧场。如果不是，考虑加入一条边，变成一个新的牧场。可以直接计算出通过这条边的最短路的最大值。 需要注意的是，通过这条边的最短路的最大值不一定是新牧场的所有最短路的最大值。这里需要比较三个值（牧场 A 的所有最短路的最大值； 牧场 B 的所有最短路的最大值， 加边后通过这条边的最短路的最大值），才能得到正确的新牧场的直径。 遍历所有点对（或者一半）， 找出 “新直径” 的最小值。 $O(n^2)$
最后的时间复杂度是 $O(n^3)$。 空间复杂度也只是 $O(n^2)$。
```cpp
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point
{
int x, y;
double distance(const Point &b)
{
return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y));
}
};
const int MAX_N = 150;
const double INF = 1e20;
int n;
int field[MAX_N] = {0};
double diameter[MAX_N + 1] = {0};
double dist[MAX_N][MAX_N];
void dfs(int i, int id)
{
field[i] = id;
for (int j = 0; j < n; ++j)
if (!field[j] && dist[i][j] < INF)
dfs(j, id);
}
int main()
{
int i, j, k;
Point a[MAX_N];
scanf("%d\n", &n);
for (i = 0; i < n; ++i)
scanf("%d %d\n", &a[i].x, &a[i].y);
char s[MAX_N + 1];
for (i = 0; i < n; ++i)
{
scanf("%s", s);
for (j = 0; j < n; ++j)
if (s[j] == '1' || i == j)
dist[i][j] = a[i].distance(a[j]);
else
dist[i][j] = INF;
}
// 1. DFS
int id = 0;
for (i = 0; i < n; ++i)
if (!field[i])
dfs(i, ++id);
// 2. Floyd-Warshall
for (k = 0; k < n; ++k)
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
// 3.4. max_sp: find max shortest path and diameter;
double max_sp[MAX_N];
for (i = 0; i < n; ++i)
{
max_sp[i] = 0.0;
for (j = 0; j < n; ++j)
if (dist[i][j] < INF)
max_sp[i] = max(max_sp[i], dist[i][j]);
diameter[field[i]] = max(diameter[field[i]], max_sp[i]);
}
// 5. find answer
double min_d = INF, max_d;
for (i = 0; i < n; ++i)
for (j = i + 1; j < n; ++j)
if (field[i] != field[j])
{
max_d = max(max(diameter[field[i]], diameter[field[j]]),
max_sp[i] + a[i].distance(a[j]) + max_sp[j]);
min_d = min(min_d, max_d);
}
printf("%.6f\n", min_d);
return 0;
}
```