A18530. 线网建设
填空题
困难
知识点
题目描述
线网建设
题目描述
A 市有 n 座基站需要通过线网互相连接。第 i 座基站位于二维平面上坐标 (xi,yi)处。
第 i 座基站与第 j 座基站之间的距离定义为 
如果两座基站之间的距离不超过给定的整数 l，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。
如果从一座基站出发，经过一系列线网中的线路可以到达另一座基站，则称这两座基站是互相连接的。
请问使得 n 座基站两两之间都互相连接，需要修建的线路总长度最小是多少？如果不能修建满足条件的线网，则输
出 Impossible 。
输入格式
第一行，两个正整数 n,l，分别表示基站数量与线路长度上限。
接下来 n 行，每行两个整数 xi,yi，表示基站的坐标。
输出格式
输出一行。如果能修建满足条件的线网，则输出需要修建的最小线路总长度，保留两位小数。否则输出
Impossible 。
样例
输入样例 1
4 2
1 0
-1 -1
0 0
1 1输出样例 1
3.41输入样例 2
4 1
1 0
-1 -1
0 0
1 1输出样例 2
Impossible数据范围
对于 40% 的测试点，保证 1 ≤ n ≤ 100。
对于所有测试点，保证 1 ≤ n ≤ 500，1 ≤ l ≤ 100，1 ≤ xi,yi ≤ 100 。
参考答案
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 510;
const int E = N * N;
int n, l;
int x[N], y[N];
int p[E], u[E], v[E], cnt;
int f[N], t = 0;
double d[E], ans = 0;
int getf(int u) {
return f[u] ? f[u] = getf(f[u]) : u;
}
bool cmp(int a, int b) {
return d[a] < d[b];
}
int main() {
cin >> n >> l;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
int dx = x[i] - x[j], dy = y[i] - y[j];
if (dx * dx + dy * dy > l * l)
continue;
cnt++;
p[cnt] = cnt;
u[cnt] = i;
v[cnt] = j;
d[cnt] = sqrt(dx * dx + dy * dy);
}
sort(p + 1, p + cnt + 1, cmp);
for (int i = 1; i <= cnt; i++) {
int pu = u[p[i]], pv = v[p[i]];
if (getf(pu) == getf(pv))
continue;
t++;
ans += d[p[i]];
f[getf(pu)] = pv;
}
if (t == n - 1)
printf("%.2lf\n", ans); else
printf("Impossible\n");
return 0;
}
上一题
下一题