P3416-图论-法1.BFS / 法2.Floyd

这道题虽然标签有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=1
    vis=[sta]
    while q:
        cur=q.popleft()
        for  nei in d[cur]:
            if nei not in vis:
                vis.append(nei)
                l+=1
                q.append(nei)
    return l

mx=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 = a
    x2, y2, d2 = b
    if (x1-x2)**2 + (y1-y2)**2 <= d1**2:
        return 1
    else:
        return 0

te = []
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)