import sys
input = sys.stdin.readline
def DFS(now):
global id,result
visited[now] = nowid = id
stack.append(now)
for next in range(N):
if graph[now][next]:
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now] == nowid:
c = 1e9
while 1:
x = stack.pop()
c = min(c,cost[x]); visited[x] = 1e9
if x==now:
result += c
return
N = int(input())
cost = [*map(int,input().split())]
graph = [[*map(int,input().strip())] for i in range(N)]
stack = []; visited = [0]*N; result = 0
for i in range(N):
if not visited[i]:
id = 1
DFS(i)
print(result)
SCC 기본문제.
타잔 알고리즘으로 해결하였다.
SCC를 구하고, 각 SCC의 요소 중 최소비용을 가진 도시에 경찰서를 세우면 된다.
오늘의 교훈) SCC 알고리즘은 매우 유용하다.