自动搬运

查看原文

来自洛谷，原作者为

	MY（一名蒟蒻） 你数据结构都用错了，怎么改都是没用的。

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

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

以下是正文

今天CSP刚报好名，刚好$\color{green}AC$ 这题。听说比赛前写题解可以＋rp，于是就有了这篇题解。

原题传送门

博客食用不知道会不会更佳

0.审题

题面前面一大堆有的没的，蛋是

当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。

一语道破目的：最小生成树。

其实你不分析题面的话也不知道。

最小生成树是什么呢，实际上就是给您一个图，要求把图变成一个由n-1（n为点数）条边组成的图，使得总边权最小。

该不会真的有人不知道最小生成树是什么就来做这题吧，不会吧不会吧（大雾

1.思路

第一反应Kruskal，于是写完一提交直接爆炸。

$\color{black}TLE+MLE$

血的教训

$\color{black}MLE$：存边数组爆炸

$\color{black}TLE$：$O(mlogm)$爆炸

于是Prim大法好啊！！！

Prim算法流程：

1. 开始将起点（本题随意）标记为蓝点；
2. 找一条连接蓝点集合中一点和白点集合中一点最短的边；
3. 将该边连接的白点加入蓝点；
4. 将该新加入的蓝点所有连接的白点最短边更新；
5. 返回第二步，直到n个点都被选入最小生成树为止。

注：蓝点为已加入最小生成树的点，白点反之。

2.代码实现

相信大家可以发现，这个算法流程跟Dijkstra差不多，于是代码实现也很相似。

因为算法流程已经给出，代码注释将不再赘述。

code:

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
int n;
typedef double dou;
dou x[5010],y[5010],dis[5010],book[5010],ans;

dou get_e(dou x1,dou y1,dou x2,dou y2)
{//求两点间距离函数
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void init()//初始化
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);
		dis[i]=1e12*1.0;//double类很大，炸不了
	}
	return ;
}

void Prim()
{
	dis[1]=0.0;
	book[1]=true;
	int curr;
	double minn;
	for(int i=1;i<=n;i++)
	{
		curr=1;
		minn=1e9*1.0;
		for(int j=1;j<=n;j++)//找最短边
			if(!book[j] && dis[j] < minn)
				minn=dis[j],curr=j;
		book[curr]=true;
		ans+=dis[curr];
		for(int j=1;j<=n;j++)//现用现算
			dis[j]=min(dis[j],get_e(x[curr],y[curr],x[j],y[j]));
	}
	printf("%.2lf",ans);
	return ;
}

int main()
{
//	freopen("work.in","r",stdin);freopen("work.out","w",stdout);
	init();
	Prim();
//	fclose(stdin);fclose(stdout);
	return 0;
}

Thank you for your reading!

拒绝白嫖，从我做起。点个赞再走嘛。