社区讨论
为什么不对啊?帮忙看一下行吗!
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 条回复,欢迎继续交流。
正在加载回复...