简单图论：聪明的猴子

解题思路

最小生成树

问题实质：构建一个连通图，使得该连通图的最长边最短。
发现：根据Kruskal算法的步骤流程，构建的Kruskal是由最短边逐次添加，即
该连通图的最长边最短。
**改动：**根据任务需求，在构建最小生成树时，每添加一组连边，则比较一下点与点之间距离，保留最大值。
根据每只猴子的最大跳远距离和最小生成树中的距离最大值的比较，计算结果。

AC_Code

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
from math import sqrt
ax = [0 for _ in range(10005)]
ay = [0 for _ in range(10005)]
e = []
f = [i for i in range(10005)]
vis = [0 for _ in range(10005)]
def js(x,y):return (ax[x]-ax[y])*(ax[x]-ax[y])+(ay[x]-ay[y])*(ay[x]-ay[y])
def getf(x):if x == f[x]:return xf[x] = getf(f[x])return f[x]
ecnt = 0
def add(u,v,w):global ecntecnt+=1e.append((u,v,w))
m = int(input())
hz = list(map(int,input().split()))
n = int(input())
for i in range(n):ax[i],ay[i] = map(int,input().split())
for i in range(n):for j in range(i+1,n):add(i+1,j+1,js(i,j))cnt = 0
ans = -1
e = sorted(e,key = lambda x:x[2])for i in range(ecnt):u,v = getf(e[i][0]),getf(e[i][1])if u!=v:cnt+=1ans = max(ans,sqrt(e[i][2]))f[u] = vif cnt==n-1:break
res = 0
for i in range(m):if ans<=hz[i]:res+=1
print(res)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！