wans038   6년 전

코사라주 알고리즘을 이용해 SCC를 구했고

하나의 SCC가 탐색 되는 각 시점에서 SCC의 원소(정점)의 가중치를 합산해서 


sccWeight[sccV] 배열을 만들었고

각 정점의 scc 번호를 저장해 O(|E|) 시간복잡도로 SCC 인접 리스트(sccAdj)를 만들었습니다.


그리고 DFS를 응용해 현재 SCC에서 현재 이 SCC에게 음식점이 있거나, 이 SCC에서 음식점이 있는 SCC로 갈 수 있는지 알 수 있는

isResSCC[sccV]를 만들었습니다.


이를 가지고 함수 f에서는 시작 정점에서 최대로 많이 인출 할 수 있는 금액을 DP를 가지고 풀었습니다.


그런데 시간초과가 뜨는 군요...

혹시 SCC간 최대 정점 가중치를 구할 수 있는 도움되는 알고리즘 있을 까요?

댓글을 작성하려면 로그인해야 합니다.