线网建设

题目描述

A 市有 $n$ 座基站需要通过线网互相连接。第 $i$ 座基站位于二维平面上坐标 $(x_i, y_i)$ 处。

第 $i$ 座基站与第 $j$ 座基站之间的距离定义为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。

如果两座基站之间的距离不超过给定的整数 $l$，那么可以修建连接这两座基站的线路，线路长度为基站间的距离。

如果从一座基站出发，经过一系列线网中的线路可以到达另一座基站，则称这两座基站是互相连接的。

请问使得 $n$ 座基站两两之间都互相连接，需要修建的线路总长度最小是多少？如果不能修建满足条件的线网，则输出 Impossible。

输入格式

第一行，两个正整数 $n, l$，分别表示基站数量与线路长度上限。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，表示基站的坐标。

输出格式

输出一行。如果能修建满足条件的线网，则输出需要修建的最小线路总长度，保留两位小数。否则输出 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 \le n \le 100$。

对于所有测试点，保证 $1 \le n \le 500$，$1 \le l \le 100$，$-100 \le x_i, y_i \le 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;
}