4013번 - ATM
코사라주 알고리즘을 이용해 SCC를 구했고
하나의 SCC가 탐색 되는 각 시점에서 SCC의 원소(정점)의 가중치를 합산해서
sccWeight[sccV] 배열을 만들었고
각 정점의 scc 번호를 저장해 O(|E|) 시간복잡도로 SCC 인접 리스트(sccAdj)를 만들었습니다.
그리고 DFS를 응용해 현재 SCC에서 현재 이 SCC에게 음식점이 있거나, 이 SCC에서 음식점이 있는 SCC로 갈 수 있는지 알 수 있는
isResSCC[sccV]를 만들었습니다.
이를 가지고 함수 f에서는 시작 정점에서 최대로 많이 인출 할 수 있는 금액을 DP를 가지고 풀었습니다.
그런데 시간초과가 뜨는 군요...
혹시 SCC간 최대 정점 가중치를 구할 수 있는 도움되는 알고리즘 있을 까요?
댓글을 작성하려면 로그인해야 합니다.
wans038 6년 전
코사라주 알고리즘을 이용해 SCC를 구했고
하나의 SCC가 탐색 되는 각 시점에서 SCC의 원소(정점)의 가중치를 합산해서
sccWeight[sccV] 배열을 만들었고
각 정점의 scc 번호를 저장해 O(|E|) 시간복잡도로 SCC 인접 리스트(sccAdj)를 만들었습니다.
그리고 DFS를 응용해 현재 SCC에서 현재 이 SCC에게 음식점이 있거나, 이 SCC에서 음식점이 있는 SCC로 갈 수 있는지 알 수 있는
isResSCC[sccV]를 만들었습니다.
이를 가지고 함수 f에서는 시작 정점에서 최대로 많이 인출 할 수 있는 금액을 DP를 가지고 풀었습니다.
그런데 시간초과가 뜨는 군요...
혹시 SCC간 최대 정점 가중치를 구할 수 있는 도움되는 알고리즘 있을 까요?