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

题目描述

小明正在参加一场爆破工作。人们在地面上放置了 $n$ 个爆炸魔法阵，第 $i$ 个魔法阵的圆心坐标为 $(x_i,y_i)$，半径为 $r_i$。如果两个魔法阵相交，则它们可以一起引爆；如果两个魔法阵不相交，则可以再使用一条魔法回路将它们的边缘连接起来。小明想知道最少需要布置总长度多长的魔法回路才能使得所有的魔法阵可以一起引爆？

输入格式

输入共 $n+1$ 行。

• 第一行为一个正整数 $n$。
• 后面 $n$ 行，每行三个整数表示 $x_i,y_i,r_i$。

输出格式

输出共 $1$ 行，一个浮点数表示答案（四舍五入保留两位小数）。

输入输出样例 #1

输入 #1

4
0 0 1
2 0 2
-3 0 1
4 4 1

输出 #1

2.47

说明/提示

样例说明

• 使用魔法回路连接第 $1$、$3$ 个魔法阵，长度为 $1$。
• 使用魔法回路连接第 $2$、$4$ 个魔法阵，长度为 $2\sqrt{5}-3=1.47$。

总长度 $2.47$。

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n\le 500$。
• 对于 $100\%$ 的评测用例，$1\le n\le 5000$，$|x_i|,|y_i|\le 2000$，$0<r_i\le 20$。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int n,m,tot,fa[maxn],cnt,x[maxn],y[maxn],r[maxn];
double sum;
double dis(int x,int y,int xx,int yy){
    return sqrt(((x-xx)*(x-xx)+(y-yy)*(y-yy))*1.0);
}
int find(int x){
	if(fa[x]==x) return fa[x];
	return fa[x]=find(fa[x]);
}
struct node{
	int u,v;
    double w;
	bool operator<(const node& b)const{
		return w<b.w;
	}
}e[12502505];
void add(int u,int v,double w){
	e[++tot]={u,v,w};
}
int main(){
	scanf("%d",&n);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=n;++i){
        scanf("%d %d %d",x+i,y+i,r+i);
        for(int j=1;j<i;++j){
            double diss=dis(x[i],y[i],x[j],y[j]);
            add(i,j,max(0.0,diss-r[i]-r[j]));
        }
    }
	sort(e+1,e+tot+1);
	for(int i=1;i<=tot;i++){
		int f=find(e[i].u),ff=find(e[i].v);
		if(f!=ff){
            fa[f]=ff;
			cnt++;
            sum+=e[i].w;
		}
		if(cnt==n-1) break;
	}
	printf("%.2lf",sum);
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容