import sys,collections
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def BFS():
result = 0; pre = [0]*C
while dq:
now = dq.popleft()
if sccrest[now]:
result = max(result,pre[now]+scc[now])
for next in sccgraph[now]:
indegree[next] -= 1
pre[next] = max(pre[next],pre[now]+scc[now])
if not indegree[next]:
dq.append(next)
return result
def DFS(now):
global id,start
visited[now] = nowid = id
stack.append(now)
for next in graph[now]:
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now] == nowid:
n = len(scc); scc.append(0)
while 1:
x = stack.pop()
scc[-1] += money[x]
sccnum[x] = n; visited[x] = 1e7
if x==now:
break
N,M = map(int,input().split())
graph = [[] for i in range(N+1)]; indegree = [0]*(N+1)
for _ in range(M):
a,b = map(int,input().split())
graph[a].append(b)
indegree[b] += 1
money = [0]+[int(input()) for i in range(N)]
S,P = map(int,input().split())
rest = [*map(int,input().split())]
stack = []; scc = []; visited = [0]*(N+1); sccnum = [0]*(N+1)
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i)
C = len(scc)
sccgraph = [[] for i in range(C+1)]
indegree = [0]*C; sccrest = [0]*(C+1); scc.append(0)
for i in range(1,N+1):
for j in graph[i]:
if sccnum[i]==sccnum[j]:
continue
sccgraph[sccnum[i]].append(sccnum[j])
indegree[sccnum[j]] += 1
for r in rest:
sccrest[sccnum[r]] = 1
sccgraph[-1].append(sccnum[S]); indegree[sccnum[S]] += 1
dq = collections.deque()
for i in range(C):
if not indegree[i]:
dq.append(i)
BFS()
dq.append(-1)
print(BFS())
SCC + 위상정렬 문제이다.
코드길이가 상당히 길고 구현량이 많다. 하지만 아이디어 자체는 쉬운 편이고 실수할 여지도 적은 편이어서 풀기 어렵지는 않다.
이 문제를 풀기 전에 위상정렬 최장거리 [백준 1005번] ACM Craft (Python3) (tistory.com) , SCC 알고리즘 [백준 2150번] Strongly Connected Component (Python3) (tistory.com) , SCC+indegree [백준 4196번] 도미노 (Python3) (tistory.com) 를 풀어본 경험이 도움이 되었다.
풀이를 설명하면,
1. 타잔 알고리즘으로 SCC를 구하고, 각 SCC의 돈의 합을 저장한다.
2. 모든 간선에 대해서 같은 SCC 내부의 간선을 제외한 나머지 간선에 대해 SCC간 그래프를 작성하고, SCC의 indegree를 구한다.
3. 시작지점 S를 포함한 SCC의 indegree를 +1 해준다.
4. SCC의 indegree가 0인 점에 대해서 BFS로 탐색한다. (이 SCC들은 쓸모없는 데이터이다. 시작지점에서 도달할 수 없기 때문)
5. 초기화 후, 이번엔 시작지점에서 BFS로 탐색하여 위상정렬+DP의 최장거리 구하는 방식으로 최대 돈을 구한다.
오늘의 교훈) 다양한 알고리즘을 적재적소에 활용하자