G8021 [GESP202606 八级] 线网建设 题解

知识点：最小生成树、Prim、欧氏距离、浮点运算。

解题思路

只允许长度不超过l的连线，使用朴素Prim：每次选未入树且连接代价最小的点，再更新它到其他点的合法欧氏距离。

为什么正确

Prim依据最小跨割边性质逐步扩展最小生成树；超过长度限制的边直接视为不存在，无法选点时图不连通。

易错点

先用平方距离判断长度限制，再开方计费用；无法连通输出Impossible，正常输出两位小数。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l;
    cin>>n>>l;
    vector<int>x(n),y(n);
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    vector<double>d(n,1e100);
    vector<int>used(n);
    d[0]=0;
    double ans=0;
    for(int k=0;k<n;k++) {
        int u=-1;
        for(int i=0;i<n;i++)if(!used[i]&&(u<0||d[i]<d[u]))u=i;
        if(d[u]>1e50) {
            cout<<"Impossible";
            return 0;
        }
        used[u]=1;
        ans+=d[u];
        for(int v=0;v<n;v++)if(!used[v]) {
            int sq=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
            if(sq<=l*l)d[v]=min(d[v],sqrt((double)sq));
        }
    }
    cout<<fixed<<setprecision(2)<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。