【Luogu P1265】公路修建

Luogu P1265

本来一开始我用的Kruskal……但是由于double类型8字节，所以MLE了。

很容易发现这是一道最小生成树的题目。

值得注意的是题目中给的第二个限制，只存在唯一情况即这个环为等边多边形。

但是如果是等边多边形那么这个限制给了和没给完全没区别……

所以这就是一道最小生成树裸题。

由于Kruskal需要记录边权进行统计，而题中给的是一个完全图，空间开销很大。

Prim可以在需要的时候进行计算，不需要提前记录，空间开销一般。

事实上这也是Prim算法和Kruskal算法原理上的不同。

Prim算法是以点为中心的算法，Kruskal是以边为中心的算法。

在稀疏图中Kruskal表现优于Prim，但在稠密图和完全图中Prim会更适合。

#include<cstdio>

#include<cmath>

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

long long n,cost[5005],x[5005],y[5005];

bool vis[5005];

double ans;

void First()

{

	for (int i=0;i<=n;i++) cost[i]=inf;

	cost[1]=0;

}

void Prim()

{

	for (int i=1;i<=n;i++)

	{

		long long mincost=inf,m=0;

		for (int j=1;j<=n;j++)

			if (mincost>cost[j]&&!vis[j])

			{

				mincost=cost[j];

				m=j;

			}

		vis[m]=true;

		ans+=sqrt(cost[m]);

		for (int j=1;j<=n;j++)

			if ((x[m]-x[j])*(x[m]-x[j])+(y[m]-y[j])*(y[m]-y[j])<cost[j]&&!vis[j])

				cost[j]=(x[m]-x[j])*(x[m]-x[j])+(y[m]-y[j])*(y[m]-y[j]);

	}

}

int main()

{

	scanf("%lld",&n);

	for (int i=1;i<=n;i++)

		scanf("%lld%lld",&x[i],&y[i]);

	First();

	Prim();

	printf("%.2f",ans);

	return 0;

}

巴特西

【Luogu P1265】公路修建

最新文章

热门文章