题解：P12158 [蓝桥杯 2025 省 Java B] 爆破

· · 题解

看完题目，要求为给定一些点，求全部连起来的最小费用。但凡是对图论有一点了解的，都知道这题应该用最小生成树的算法。

确定算法后，就很好考虑了。

首先考虑如何建边。我们的边是任意两点之间都会有，不存在无法连边的情况。那么每条边的边权如何计算呢？

则可以再使用一条魔法回路将它们的边缘连接起来。

所以，边权是任意两个点所形成的圆的边缘的最短距离。计算方法是把两点距离算出来，再减去两条半径。注意，如果这个算出来的距离为负的话，

如果两个魔法阵相交，则它们可以一起引爆；

即最后赋的边权为零，不需要任何费用。

其次，建好边后，考虑如何套最小生成树的算法。经过思考，发现没有需要特别修改的地方，那就可以直接套模板。注意，一些关键变量和存图时要用 double 类型。

自认为代码风格还是非常工整的。最小生成树算法我用的是 prim。

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int n,zn[N][3],vis[N],v,u;
double l,ans[N],maxn,w;
vector<double> ag[N][2];
double dis(int x1,int y1,int x2,int y2,int r1,int r2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-r1-r2;
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>zn[i][0]>>zn[i][1]>>zn[i][2];
        for(int j=1;j<i;j++){
            l=dis(zn[i][0],zn[i][1],zn[j][0],zn[j][1],zn[i][2],zn[j][2]);
            if(l<=0) l=0;
            ag[i][0].push_back(j);
            ag[i][1].push_back(l);
            ag[j][0].push_back(i);
            ag[j][1].push_back(l);
        }
    }
    for(int i=2;i<n+2;i++) ans[i]=INT_MAX;
    while(1==1){
        u=n+1;
        for(int i=1;i<=n;i++)
            if(vis[i]==0&&ans[u]>ans[i]) u=i;
        if(u==n+1) break;
        vis[u]=1,maxn+=ans[u];
        for(int i=0;i<ag[u][0].size();i++){
            v=ag[u][0][i],w=ag[u][1][i];
            ans[v]=min(ans[v],w);
        }
    }
    printf("%.2lf",maxn);
}