是,我也有这个疑问
by LSY_NY @ 2024-04-14 16:44:40
我也想问,为啥这是对的?
**AC代码:**
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5;
struct Edge{
int from, to;
double w;
};
struct Node{
int x, y;
};
Node a[N];
Edge e[M];
bool cmp (const Edge& a, const Edge& b) {
return a.w < b.w;
}
int f[N];
int find(int x) {
if (f[x] == x) return x;
else {
int j = find(f[x]);
f[x] = j;
return j;
}
}
int n, s;
int m, cnt;
double ans[N];
void kruscal() {
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1; i <= m; i++) {
int x = find(e[i].from), y = find(e[i].to);
if (x != y) {
f[x] = y;
cnt++;
ans[cnt] = e[i].w;
}
}
}
int main(){
scanf("%d%d", &s, &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &a[i].x, &a[i].y);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
m++;
e[m].from = i, e[m].to = j;
e[m].w = sqrt(abs(a[i].x - a[j].x) * abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y) * abs(a[i].y - a[j].y));
}
}
kruscal();
printf("%.2lf", ans[n - s]);
return 0;
}
```
by nyyyh @ 2024-04-14 16:46:29
卫星电话是两两联通还是全部都可以互相联通
by Unicorn_Conspiracy @ 2024-04-14 16:46:48
全部吧~~我觉得~~,可有啥关联呢?
by nyyyh @ 2024-04-14 16:50:38