求助,样例都没过……
  • 板块P1433 吃奶酪
  • 楼主lizichang
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/3/28 21:29
  • 上次更新2023/11/5 01:25:07
查看原帖
求助,样例都没过……
373819
lizichang楼主2021/3/28 21:29
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct Edge
{
	double u,v,w;
}edge[5000000];
struct node
{
	int x,y;
}a[1005];
double ans=0;
int fa[2005],cnt=0,m,n,eu,ev,stop=0;
int find(int p)
{
	while(p!=fa[p])	p=fa[p]=fa[fa[p]];
	return p;
}
//并查集循环实现,及路径压缩
int cmp(Edge x,Edge y)
{
	return x.w<y.w;
}
//快排的依据(按边权排序)
void kruskal()
{
	sort(edge+1,edge+cnt+1,cmp);
	//将边的权值排序
	for(int i=1;i<=cnt;i++)
	{
		eu=find(edge[i].u),ev=find(edge[i].v);
		if(eu==ev)	continue;
		//若出现两个点已经联通了,则说明这一条边不需要了
		fa[eu]=ev;
		ans+=edge[i].w;
		//将此边权计入答案
		if(++stop==n-1)	break;
		//循环结束条件,及边数为点数减一时
	}
}
int main()
{
	cin>>n;
	n++;
	for(int i=1;i<=n;i++)	fa[i]=i;
	//初始化并查集
	int x,y;
	for(int i=1;i<=n-1;i++)
		a[i].x=read(),a[i].y=read();
	a[n].x=0,a[n].y=0;
	for(int i=1;i<=n;i++)//计算两点距离 
	{
		for(int j=1;j<i;j++)
		{
			edge[++cnt].w=sqrt(1.0*(fabs(a[i].x-a[j].x)*fabs(a[i].x-a[j].x))+(fabs(a[i].y-a[j].y)*fabs(a[i].y-a[j].y)));
			edge[cnt].u=i;
			edge[cnt].v=j;
			cout<<edge[cnt].w<<endl;
		}
	}
	kruskal();
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}
2021/3/28 21:29
加载中...