P2504 40pcs蒟蒻求助
  • 板块题目总版
  • 楼主Gym081030
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/10 17:43
  • 上次更新2023/10/27 21:12:36
查看原帖
P2504 40pcs蒟蒻求助
525545
Gym081030楼主2022/7/10 17:43
#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans;
int num,cnt,sum;
int x[100001],y[100001];
int f[100001],a[100001];
typedef struct Node
{
    int u;
    int v;
    double w;
}Edge;
Edge e[1000001];
void quicksort(int left,int right)
{
    int i,j;
    if(left>right)
        return;
    i=left;
    j=right;
    while(i!=j)
    {
        while(e[j].w>=e[left].w && i<j)
            j--;
        while(e[i].w<=e[left].w && i<j)
            i++;
        if(i<j)
            swap(e[i],e[j]);
    }
    swap(e[i],e[left]);
    quicksort(left,i-1);
    quicksort(i+1,right);
}
int find(int v)
{
    return f[v]==v?v:f[v]=find(f[v]);
}
inline bool merge(int u,int v)
{
    if(find(u)!=find(v))
    {
        f[find(u)]=find(v);
        return true;
    }
    return false;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=m-1;i++)
        for(int j=i+1;j<=m;j++)
        {
            e[++num].u=i;
            e[num].v=j;
            e[num].w=(double)sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j]));
        }
    quicksort(1,num);
    for(int i=1;i<=num;i++)
    {
        if(merge(e[i].u,e[i].v))
        {
            cnt++;
            ans=max(ans,e[i].w);
        }
        if(cnt==n-1){
            break;
        }
    }
    for(int i=1;i<=n;i++)
        if(a[i]*1.0>=ans)
            sum++;
    cout<<sum;
    return 0;
}
2022/7/10 17:43
加载中...