Kruskal十分求助
查看原帖
Kruskal十分求助
430409
Coros_Trusds楼主2021/3/19 13:21

已经把自己的代码按照题解顶楼的代码改了一下,为什么题解的代码可以AC,我的代码只有十分?

难道是read()的问题??

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

int n,m;

int cnt,sum;

double ans;

int f[1000005];

struct zuobiao
{
	int x,y;
};

zuobiao zb[1000005];

struct node
{
	int u;
	
	int v;
	
	double w;
};

node e[1000005];

inline double dist(int x,int y)
{
	return (double)(sqrt((double)(zb[x].x-zb[y].x)*(zb[x].x-zb[y].x))+(double)(zb[x].y-zb[y].y)*(zb[x].y-zb[y].y)); 
}

inline void add(int x,int y,double z)
{
	cnt++;
	
	e[cnt].u=x;
	
	e[cnt].v=y;
	
	e[cnt].w=z;
}

inline bool cmp(node x,node y)
{
	return x.w<y.w;
}

inline int get(int x)
{
	if(f[x]==x)
	{
		return x;
	}
	
	return f[x]=get(f[x]);
}

inline void merge(int x,int y)
{
	int f1=get(x);
	
	int f2=get(y);
	
	if(f1!=f2)
	{
		f[f1]=f2;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	
	for(register int i=1;i<=n;i++)
	{
		scanf("%d%d",&zb[i].x,&zb[i].y);
	}
	
	for(register int i=1;i<=n;i++)
	{
		f[i]=i;
	}
	
	for(register int i=1;i<=n;i++)
	{
		for(register int j=i+1;j<=n;j++)
		{
			double xx=dist(i,j);
			
			add(i,j,xx);
		}
	}
	
	for(register int i=1;i<=m;i++)
	{
		int x,y;
		
		scanf("%d%d",&x,&y);
		
		add(x,y,0.0);
	}
	
	sort(e+1,e+cnt+1,cmp);
	
	for(register int i=1;i<=cnt;i++)
	{
		if(get(f[e[i].u])!=get(f[e[i].v]))
		{
			sum++;
			
			ans+=e[i].w;
			
			merge(e[i].u,e[i].v);
		}
		
		if(sum==n-1)
		{
			break;
		}
	}
	
	printf("%.2f\n",ans);
	
	return 0;
}
2021/3/19 13:21
加载中...