[HAOI2006]聪明的猴子

/*
找出能连通所有点的一棵树 是的最大的边最小
很显然就是最小生成树. 堆优化prim.
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 1010
#define inf 999999999
using namespace std;
int n,m,num,head[maxn],ans,tot;
bool f[maxn];
double x[maxn],y[maxn],v[maxn],dis[maxn],maxx;
struct edge
{
int u,v,pre;
double t;
}e[maxn*maxn];
struct node
{
int ki,si;
node (int kk,int ss):ki(kk),si(ss) {};
bool operator < (const node & a) const
{
return si>a.si;
}
};
priority_queue<node>q;
double Get_dis(int a,int b,int c,int d)
{
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
double min(double a,double b)
{
return a>b?a:b;
}
void Add(int from,int to,double dis)
{
num++;e[num].u=from;e[num].v=to;e[num].t=dis;
e[num].pre=head[from];head[from]=num;
}
void Prim()
{
for(int i=;i<=n;i++)dis[i]=inf;
q.push(node(,));dis[]=;
while(!q.empty()&&tot<n)
{
int k=q.top().ki;q.pop();
if(f[k])continue;f[k]=;
maxx=max(maxx,dis[k]);tot++;
for(int i=head[k];i;i=e[i].pre)
{
int v=e[i].v;
if(dis[v]>e[i].t)
{
dis[v]=e[i].t;
q.push(node(v,dis[v]));
}
}
}
}
int main()
{
scanf("%d",&m);
for(int i=;i<=m;i++)
scanf("%lf",&v[i]);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j)continue;
double tmp=double(Get_dis(x[i],y[i],x[j],y[j]));
Add(i,j,tmp);
}
Prim();
for(int i=;i<=m;i++)
if(v[i]>=maxx)
ans++;
printf("%d\n",ans);
return ;
}
上一篇:jquery ajax load


下一篇:Dictionary集合运用