[boj 4013] ATM

문제 링크

 

문제를 크게 아래와 같이 나눌 수 있다.

 

1. SCC를 통해서 그룹 만들기

2. 각 그룹이 가지고 있는 ATM 현금 보유량 구하기

3. 각 그룹에 레스토랑이 있는지

4. 각 그룹을 노드로 위상정렬하여 가장 많은 현금을 챙길 수 있는 방법 구하기

 

애먹었던 부분은 4번인데, 위상정렬하여 방문을 최적화하지 않아서, 시간초과를 먹었다... python으로 시간초과 되면 괜히 python 때문인것 같다... 미안하다 python아, 내가 최적화를 못 한 잘못인데...

 

 

import sys
from collections import deque
sys.setrecursionlimit(300_000)
input = sys.stdin.readline


def scc(n, V, G, F, S):
    global o, group_n
    
    p = V[n] = o = o+1
    S.append(n)
    
    for x in G[n]:
        if V[x] == -1:
            p = min(p, scc(x, V, G, F, S))
        elif F[x] == -1:
            p = min(p, V[x])
            
    if p == V[n]:
        while S:
            c = S.pop()
            F[c] = group_n
            if c == n:
                break
        group_n += 1
    
    return p


def solve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N+1)]
    cash = [0] * (N+1)
    restaurant = [0] * (N+1)
    
    for _ in range(M):
        u, v = map(int, input().split())
        G[u].append(v)
    
    for idx in range(N):
        cash[idx+1] = int(input())
    
    s, p = map(int, input().split())
    
    temp = list(map(int, input().split()))
    
    for t in temp:
        restaurant[t] = 1
        
    V = [-1] * (N+1)
    F = [-1] * (N+1)
    S = []
    
    global o, group_n
    o = 0
    group_n = 1
    
    
    for n in range(1, N+1):
        if V[n] == -1: scc(n, V, G, F, S)
        
    group_cash = [0] * group_n
    group_graph = [[] for _ in range(group_n)]
    group_restaurant = [0] * group_n
    
    for n in range(1, N+1):
        group = F[n]
        group_cash[group] += cash[n]
        if restaurant[n]: group_restaurant[group] = 1
        
        for x in G[n]:
            if group != F[x]: group_graph[group].append(F[x])
    
    V = [0] * group_n
    s = F[s]
    V[s] = 1
    
    S = [s]

    while S:
        n = S.pop()
        for x in group_graph[n]:
            if not V[x]:
                V[x] = 1
                S.append(x)
                
    indegree = [0] * group_n
    for n in range(1, group_n):
        if not V[n]: continue
        for x in group_graph[n]:
            if V[x]: indegree[x] += 1
            
    dp = [-1] * group_n
    dp[s] = group_cash[s]
    
    q = deque([s])
    
    while q:
        n = q.popleft()
        
        for x in group_graph[n]:
            dp[x] = max(dp[x], dp[n] + group_cash[x])
                
            indegree[x] -= 1
            
            if not indegree[x]: q.append(x)
            
    ans = 0
    
    for idx in range(1, group_n):
        if group_restaurant[idx]: ans = max(ans, dp[idx])
        
    print(ans)

    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()

수 많은 트라이들...