题解 P2504 【[HAOI2006]聪明的猴子】
sukimo
2020-04-26 21:57:35
这道题只要理清了思路，就会发现是MST裸题。MST具有的一个性质：“MST的最大边权是这个图所有生成树的最大边权中最小的。”对于一只猴子，它能否跳到每棵树上，取决于它跳跃的生成树的最大边权是否会超过它的跳跃限度，而MST可以做到“最大边权最小”，如果某只猴子按照MST来跳跃，就可以尽量的把跳跃的最大边权控制到最小，这样就很好的划分出来了。先用prim求出MST（不用kruskal的原因是kruskal是把所有的边全部弄出来再做，而prim是边做边求，不会浪费兀余的的空间），边做边找到最大边权，然后对于每只猴子比较一下就好了。代码见下：
```
#include<bits/stdc++.h>
#define db double
using namespace std;
const int INF=0x3f3f3f3f;db MST_max,dis[1005],vis[1005];int n,jump[505];
struct STR1{db x,y;}pos[1005];struct STR2{int ind;db num;};
STR2 pack(int ind,db num){STR2 a;a.ind=ind;a.num=num;return a;}
struct HEAP{
int tail;STR2 tree[5000005];HEAP(){tail=0;}
STR2 _top(){return tail?tree[1]:pack(-1,INF);}
void _insert(STR2 q){
tree[++tail]=q;int p=tail;
while(p>1&&tree[p].num<tree[p>>1].num){swap(tree[p],tree[p>>1]);p>>=1;}
}
void _delete(){
tree[1]=tree[tail--];int p=1;
while(p<<1<=tail){
int son=p<<1;if(son<tail&&tree[son].num>tree[son+1].num)son++;
if(tree[son].num>=tree[p].num)break;
swap(tree[son],tree[p]);p=son;
}
}
}heap;
db solve(int a,int b){return sqrt((pos[a].x-pos[b].x)*(pos[a].x-pos[b].x)+(pos[a].y-pos[b].y)*(pos[a].y-pos[b].y));}
void prim(){
heap._insert(pack(1,0));for(int i=2;i<=n;i++)dis[i]=INF;
for(int i=1;i<=n;i++){
while(vis[heap._top().ind])heap._delete();
STR2 q;q=heap._top();MST_max=max(MST_max,dis[q.ind]);dis[q.ind]=0;vis[q.ind]=1;
for(int j=1;j<=n;j++)
if(solve(q.ind,j)<dis[j])heap._insert(pack(j,dis[j]=solve(q.ind,j)));
}
}
int main(){
int m,cnt=0;scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&jump[i]);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&pos[i].x,&pos[i].y);
prim();
for(int i=1;i<=m;i++)if(MST_max<=jump[i])cnt++;
printf("%d",cnt);
return 0;
}
```