思路
对于每个连通块求出任意两点距离的最大值 \(max[u]\),然后再 \(O(n^2)\) 枚举任意两个连通块连接起来,答案就是两个连通块的最大值 \(max\) 加上中间连接的边的长度。
代码
#include <bits/stdc++.h>
using namespace std;
using PDD = pair<double, double>;
const int N = 160;
int fa[N];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return;
fa[fx] = fy;
}
int n;
PDD a[N];
double dis[N][N], maxd[N];
double zjd[N];
double gdis(PDD a, PDD b) {
return sqrt(((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second)));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char c;
cin >> c;
if (c == '1') {
dis[i][j] = gdis(a[i], a[j]);
merge(i, j);
}
else dis[i][j] = 1e18;
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i][j] > dis[i][k] + dis[k][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int fx = find(i), fy = find(j);
if (fx == fy && i != j) {
zjd[fx] = max(dis[i][j], zjd[fx]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j && find(i) == find(j) && dis[i][j] < 1e17) maxd[i] = max(maxd[i], dis[i][j]);
}
}
double ans = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (find(i) == find(j)) continue;
ans = min(ans, max(max(zjd[find(i)], zjd[find(j)]), maxd[i] + maxd[j] + gdis(a[i], a[j])));
}
}
printf("%.6lf", ans);
return 0;
}
标签:return,Cow,int,fa,second,Tours,USACO2.4,first,dis
From: https://www.cnblogs.com/Yuan-Jiawei/p/18348604