社区讨论
救命啊!这题有毒
P2504[HAOI2006] 聪明的猴子参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6oi126
- 此快照首次捕获于
- 2025/11/20 08:14 4 个月前
- 此快照最后确认于
- 2025/11/20 08:14 4 个月前
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct mon
{
long x;
long y;
long v;
};
long max(long a,long b)
{
return a>b?a:b;
}
long father[10005];
long find(long x)
{
if(father[x]!=x)
father[x]=find(father[x]);
return father[x];
}
bool cmp(mon a,mon b)
{
return a.v<b.v;
}
int main()
{
struct mon a[10005];
long o=0,temp=0,ans=0,i,j,n,m;
long monkey[10005],x[10005],y[10005];
cin>>n;
for(i=1;i<=n;i++)
{
cin>>monkey[i];
father[i]=i;
}
cin>>m;
for(i=1;i<=m;i++)
cin>>x[i]>>y[i];
for(i=1;i<=m;i++)
for(j=i+1;j<=m;j++)
{
long tx,ty,tv;
tx=x[i]-x[j];
ty=y[i]-y[j];
tv=sqrt(tx*tx+ty*ty);
o++;
a[o].x=i;
a[o].y=j;
a[o].v=tv;
}
sort(a+1,a+o+1,cmp);
for(i=1;i<=o;i++)
{
long r1,r2;
r1=find(a[i].x);
r2=find(a[i].y);
if(r1!=r2)
{
father[r1]=r2;
temp=max(temp,a[i].v);
}
}
for(i=1;i<=n;i++)
if(monkey[i]>temp)
ans++;
cout<<ans<<endl;
return 0;
}
请大佬帮忙差错
回复
共 2 条回复,欢迎继续交流。
正在加载回复...