這道題雖然標簽有floyd但是直接bfs也能過
其實事實證明還是bfs快，因為bfs只需要遍歷特定的點，但是floyd需要考慮遍歷所有可能的中介點
法1.BFS
用字典存儲每個點所能普及的范圍，然后用對每個點bfs進行拓展
n=int(input())temp=[]#xmax=0;ymax=0
for i in range(n):te=list(map(int,input().split()))'''xmax=max(xmax,te[0])ymax=max(ymax,te[1])'''temp.append(te)'''沒必要建圖
ma=[[0]*(ymax+1) for i in range(xmax+1)]for i in range(n):ma[temp[i][0]][temp[i][1]]=temp[i][2]for i in ma:print(*i)
'''from collections import defaultdict
d=defaultdict(list)
for i in range(n):for j in range(n):if i!=j:x1,y1=temp[i][0],temp[i][1]x2,y2=temp[j][0],temp[j][1]if (x1-x2)**2+(y1-y2)**2<=temp[i][2]**2:d[i].append(j)
from collections import deque
def bfs(sta):q=deque([sta])l=1vis=[sta]while q:cur=q.popleft()for nei in d[cur]:if nei not in vis:vis.append(nei)l+=1q.append(nei)return lmx=0
for i in range(n):mx=max(mx,bfs(i))
print(mx)法2.Floyd?
用con存儲了能否到達
預處理里面我們將可以直接到達的設為1
然后用floyd算法去遍歷中介點，將可以通過中介點到達的設為1
最后我們只需要一行行地sum( )來統計每個個體所能到達的總數
注意：不能一列列遍歷，因為我們con[ i ][ j ]存儲的是從 i 到 j 的可能性，是有向的
n = int(input())def dis(a, b): # a到b單向x1, y1, d1 = ax2, y2, d2 = bif (x1-x2)**2 + (y1-y2)**2 <= d1**2:return 1else:return 0te = []
for i in range(n):te.append(tuple(map(int, input().split())))# 用tuple才能在dis中解包con = [[0]*n for i in range(n)]
#預處理
for i in range(n):for j in range(n):con[i][j] = dis(te[i], te[j])#floyd 考慮中介點情況
for k in range(n):for i in range(n):for j in range(n):con[i][j] = con[i][j] or (con[i][k] and con[k][j])ans = 0
for i in range(n):vis = sum(con[i]) # 計算每頭奶牛能通信的數量ans = max(ans, vis) # 更新最大值print(ans)
