自动搬运

查看原文

来自洛谷，原作者为

	Dicer_L 这点普及组水平还天天想着进集训队？进集八队还挺合适||头像是本人||蓝金勾无条件壶关

搬运于2025-08-24 23:13:15，当前版本为作者最后更新于2025-05-20 20:09:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

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

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

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

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