社区讨论

为什么不对啊?帮忙看一下行吗!

P2504[HAOI2006] 聪明的猴子参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7vx277
此快照首次捕获于
2025/11/21 04:29
4 个月前
此快照最后确认于
2025/11/21 04:29
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,num;
int o,p,k,tot=1,fa[2000001],b[2001],c[501],d[501];
double ans;
struct node
{
	int x,y;
	double z;
}a[2000001];// x左端点 y右端点 z权值
inline double lenth(int x,int y)
{
	double o=sqrt((c[x]-c[y])*(c[x]-c[y])+(d[x]-d[y])*(d[x]-d[y]));
	return o;
}
inline bool cmp(node a,node b)
{
	return a.z<b.z;
}// 权值从小到大排序
inline int find(int x)
{
	if(fa[x]==x) return fa[x];
	fa[x]=find(fa[x]);
	return fa[x];
}
inline void work()
{
	sort(a+1,a+1+num,cmp);
	for(int i=1;i<=num;i++) fa[i]=i;
	while(tot<n)
	{
		k++;
		o=find(a[k].x),p=find(a[k].y);
		if(fa[o]!=fa[p])
		{
			ans=a[k].z;
			fa[o]=p;
			tot++;
		}
	}
	int l=0;
	for(int i=1;i<=m;i++)
	{
		if(b[i]>=ans) l++;
	}
	cout<<l<<endl;
}
inline void write()
{
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i]>>d[i];
	}
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	{
		if(i!=j)
		{
			a[++num].x=i;a[num].y=j;
			a[num].z=lenth(i,j);
		}
	}
	work();
}
int main()
{
	write();
	return 0;
}
帮下忙感激不尽~

回复

5 条回复,欢迎继续交流。

正在加载回复...