解题思路
要保证图是强连通的，用因为给出的边全部都是双向边。考虑树形的结构，在一棵树上的$N$个节点一定是强连通的。他们都能够互相到达。又要保证树上的$n-1$条边中的最长的一条边最小。那就用Kruskal求一个最小生成树，找出其中的最长边，平方就是答案
附上代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e3+
3;
int n, x[maxn], y[maxn], cnt, tot, f[maxn];
double Ans, d[maxn][maxn];
struct Edge {
int u, v;
double w;
}ed[maxn *
maxn];
inline bool cmp(Edge a, Edge b) {
return a.w <
b.w;
}
inline int find(
int x) {
if(x == f[x])
return x;
else return f[x] =
find(f[x]);
}
inline void Kruskal() {
for(
int i=
1; i<=n; i++) f[i] =
i;
for(
int i=
1; i<=n; i++
) {
for(
int j=
1; j<=n; j++
) {
if(i !=
j) {
++
cnt;
ed[cnt].u = i, ed[cnt].v = j, ed[cnt].w =
d[i][j];
//printf("%d %d %.2lf\n", ed[cnt].u, ed[cnt].v, ed[cnt].w);
}
}
}
sort(ed+
1, ed+
1+
cnt, cmp);
for(
int i=
1; i<=cnt; i++
) {
int xx = find(ed[i].u), yy =
find(ed[i].v);
if(xx !=
yy) {
f[xx] =
find(yy);
tot ++
;
Ans =
ed[i].w;
}
if(tot == n-
1) {
break;
}
}
}
int main() {
scanf("%d", &
n);
for(
int i=
1; i<=n; i++
) {
scanf("%d%d", &x[i], &
y[i]);
}
for(
int i=
1; i<=n; i++
) {
for(
int j=
1; j<=n; j++
) {
d[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-
y[j]));
//printf("%.2lf ", d[i][j]);
}
//printf("\n");
}
Kruskal();
printf("%.0lf", Ans *
Ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9463802.html
