算法:Floyed + 最短路
时间复杂度:$O(N^3)$
这题的思路是比较简单的,但是如果对图不是很熟,建议先看一下 算法基础课 Floyed 算法
该题是有两个连通块的,最大直径最小可能包含新边(连接两个连通块的边),也可能不包含新边,两者之间取一个最大值就是该题的答案。
不包含新边的直径取为 $r2$,因为连通块已经确定,所以直接在两个连通块中取一个较大直径即为 $r2$。
包含新边即新边一定会加上,除此之外,新边的两个端点在此设为 $i$ 和 $j$,以 $i$ 点出发寻找一个最大值,以 $j$ 点出发也寻找一个最大值,三者相加即为当前加上新边的直径,在此枚举一个最小直径即为 $r1$。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 200, INF = 1e9;
int n;
double dist[N][N], maxd[N];
string g[N];
struct point {
int x, y;
}q[N];
double get_dist(point& a, point& b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> q[i].x >> q[i].y;
}
for (int i = 0; i < n; ++i) {
cin >> g[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) {
dist[i][j] = 0;
}
else if (g[i][j] == '1') {
dist[i][j] = get_dist(q[i], q[j]);
}
else {
dist[i][j] = INF;
}
}
}
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]); // floyed 求最短路
}
}
}
double r1 = INF, r2 = 0; // r1 -> min, r2 -> max
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] < INF / 2) {
maxd[i] = max(maxd[i], dist[i][j]); // 预处理 maxd[]
}
}
r2 = max(r2, maxd[i]);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dist[i][j] > INF / 2) {
r1 = min(r1, maxd[i] + get_dist(q[i], q[j]) + maxd[j]);
}
}
}
printf("%lf\n", max(r1, r2));
return 0;
}