AcWing 2681. 聪明的猴子 (kruskal算法求最小生成树)C++
原题链接
中等
作者:
xirang_hu
,
2024-04-12 23:46:36
,
所有人可见
,
阅读 6
聪明的猴子
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1005;
struct node
{
int x,y;
double w;
}e[1000005];
int n,m;
int a[N],x[N],y[N],fa[N];
// 最小生成树由并查集构建
void init()
{
for(int i=1;i<=n;i++) fa[i] = i;
}
int find(int x)
{
if(x==fa[x]) return x;
else return find(fa[x]);
}
void merge(int x,int y)
{
int xx = find(x);
int yy = find(y);
if(xx!=yy) fa[xx] = yy;
}
bool cmp(node x,node y)
{
return x.w<y.w;
}
int main()
{
cin>>m;
int cnt = 0;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
// 开始构建最小生成树
// 初始化
init();
// 添加边
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
double w = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])* ( y[i]-y[j] ));
e[++cnt] = {i,j,w};
}
}
// 排序
sort(e+1,e+1+cnt,cmp);
double maxv = 0.0;
int num = 0;
// 判断是否是连通
for(int i=1;i<=cnt;i++)
{
if(find(e[i].x)!=find(e[i].y))
{
merge(e[i].x,e[i].y);
num++;
maxv = maxv >= e[i].w ? maxv : e[i].w;
}
if(num==n-1) break;
}
int ans = 0;
for(int i=1;i<=m;i++)
{
if(a[i]>=maxv) ans++;
}
cout<<ans;
return 0;
}