求有多少只猴子可以在所有树上跳来跳去。

  求出图的最小生成树，因为最小生成树是一颗瓶颈生成树（树上最大边权最小），记录下这棵树的最大边权。因为猴子是一条一条边跳的，所以只要猴子能越过这条边，就能越过所有的边，进而到达所有的树。

 

// q.c#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int M=1000+10;struct Edge {	int u,v; double w;	Edge():u(0),v(0),w(0) {}	bool operator < (const Edge &A) const {		return w
          
           >1];int m,n,cnt,w[M],x[M],y[M],fa[M],ans;void add_edge(int a,int b,double c) { ed[++cnt].u=a,ed[cnt].v=b,ed[cnt].w=c;}double dis(int a,int b) { return sqrt((x[a]-x[b])*(x[a]-x[b])*1.0+(y[a]-y[b])*(y[a]-y[b]));}int find(int a) { return fa[a]==a?a:fa[a]=find(fa[a]);}double kruscal() { sort(ed+1,ed+cnt+1); int k=1; double maxx=0; for(int i=1;i<=cnt;i++) { Edge p=ed[i]; int fu=find(p.u); int fv=find(p.v); if(fu==fv) continue; fa[fu]=fv; ++k; if(k==n) { // ~~~if(k==n-1)~~~ maxx=p.w; break; } } return maxx;}int main() { freopen("monkey.in","r",stdin); freopen("monkey.out","w",stdout); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&w[i]); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]),fa[i]=i; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) add_edge(i,j,dis(i,j)); double maxx=kruscal(); for(int i=1;i<=m;i++) if(w[i]>=maxx) ans++; printf("%d\n",ans); return 0;}