求助:kruskal90分,最后一点MLE
查看原帖
求助:kruskal90分,最后一点MLE
411997
noctuque楼主2021/11/13 10:30
#include<bits/stdc++.h>
using namespace std;
int n,m,mm;

double tot=0.0;

struct po
{
	int x,y;
	double z;
}a[1000005];

double node[1005][2];
int fa[1005];

int find(int x)
{
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}

bool cmp(po a, po b)
{
	if(a.z==b.z)return a.x<b.x;
	return a.z<b.z;
}

void unionn(int x,int y)
{
	fa[find(x)]=fa[y];
}

int main()
{
	//freopen("11.in","r",stdin);
	//freopen("11.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	int k=m;
	
	for(int i=1;i<=n;i++) scanf("%lf%lf",&node[i][0],&node[i][1]),fa[i]=i;
	
	for(int i=1;i<=n;i++)
	{
		
		for(int j=1;j<=n;j++)
		{
			mm++;
			a[mm].x=i;a[mm].y=j;
			a[mm].z=abs(node[i][0]-node[j][0])*abs(node[i][0]-node[j][0])+abs(node[i][1]-node[j][1])*abs(node[i][1]-node[j][1]);
		}
		
	}
	
	sort(a+1,a+1+mm,cmp);
	
	for(int i=1,u,v;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		unionn(u,v);
	}
	
	for(int i=1;i<=mm;i++)
	{
		int fx=find(a[i].x),fy=find(a[i].y);
		if(fx!=fy)
		{
			fa[fx]=fy;
			tot+=sqrt(a[i].z);
			k++;
		}
		
		if(k==n-1)break;
	}
	
	printf("%.2lf\n",tot);
}
2021/11/13 10:30
加载中...