50分求助
查看原帖
50分求助
407417
HerikoDeltana楼主2021/3/24 20:23

RT

#include <bits/stdc++.h>
#define Heriko return
#define Deltana 0
#define LL long long
#define R register
#define I inline
using namespace std;
struct wood
{
	int x,y;double z;
}g[1000015];
int n,m,f[1000015],h[1000015],k[1000015][10],ln=0,xx=0,ans=0;double sum=-1;;
I int find(R int a)
{
	if(f[a]!=a) f[a]=find(f[a]);
	Heriko f[a];
}
I void uni(R int a,R int b)
{
	R int la=find(a);
	R int lb=find(b);
	f[la]=lb;
}
I int cmp(wood a,wood b)
{
	Heriko a.z<b.z;
}
signed main()
{
	scanf("%d",&n);
	for(R int i=1;i<=n;i++) f[i]=i;
	for(R int i=1;i<=n;i++) scanf("%d",&h[i]);
	scanf("%d",&m);
	for(R int i=1;i<=m;i++) scanf("%d%d",&k[i][1],&k[i][2]);
	for(R int i=1;i<=m;i++)
	{
		for(R int j=1;j<=m;j++)
		{
			if(i!=j)
			{
				ln++;
				g[ln].x=i;
				g[ln].y=j;
				g[ln].z=sqrt((k[i][1]-k[j][1])*(k[i][1]-k[j][1])+(k[i][2]-k[j][2])*(k[i][2]-k[j][2]));
			}
		}
	}
 	sort(g+1,g+1+ln,cmp);xx=m;
 	for(R int i=1;i<=ln;i++)
 	{
	 	if(xx==1) break;
		if(find(g[i].x)!=find(g[i].y))
		{
			uni(g[i].x,g[i].y);
			xx--;
			sum=g[i].z;
		}
		
	}
	for(R int i=1;i<=n;i++)
		if(sum<=h[i]) ans++;
	printf("%d",ans);
    Heriko Deltana;
}

2021/3/24 20:23
加载中...