위상정렬9 BOJ 1948 - 임계경로 (위상정렬) https://www.acmicpc.net/problem/1948 작업 https://suuntree.tistory.com/119문제의 응용 DAG(무사이클방향그래프)임이 보장됨. 시작점 ~ 도착점까지 최장거리를 구하고, 그 경로를 모두 칠했을 때 칠해진 간선의 수를 구하는 문제. 최장거리를 구하고 d배열 초기화 하는 것은 '작업' 문제와 동일함. 경로를 칠하는 것은 역방향 으로 정점을 순회하면서 d[next] = d[curr]+ weight(curr~next) 인 경우만 dfs로 따라가 주면 된다. 위 그림은 예제를 그대로 그린 것이다. 최장 경로는 12이므로, (7,2) 간선은 포함되지 않는다. 유의할 점은 이미 방문된 정점을 재 방문 하는 경우가 생긴다는 것이다. 위 예제에서 (7,2) 간선도 유효.. 2020. 1. 4. BOJ 2056 - 작업 (위상정렬) https://www.acmicpc.net/problem/2056 오랜만에 그래프문제 최대 10000개 작업들의 순서와 각 작업을 수행하는 데 걸리는 시간이 주어질 때 모든 작업이 끝나는데 걸리는 시간을 구해라. 예제의 상황을 그래프로 그리면 다음과 같다. 5번 작업을 수행하기 위해선 2번과 4번 작업이 모두 끝나야 한다. 1. i번까지 작업을 완료하는데 걸리는 시간을 d[i]라고 하고, 처음에 0으로 초기화 한다. 2. ind[i] == 0 인 정점들만 작업하는데 걸리는 시간으로 d를 초기화 한다. 3. 위상정렬된 순서대로 정점들을 방문하면서 d[next] = max(d[next], d[curr]+work[next])로 초기화해준다. 4. 위상정렬 후 d[i]중 최대값을 출력한다. #include #i.. 2020. 1. 4. BOJ 4013 - ATM https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어 www.acmicpc.net 중요한 문제라고 생각함. 유니온파인드 말고 SN, sn[MAX] 쓰면 더 쉽다. scc를 나누는데 레스토랑이 있는지, 시작점인지 등등 정보.. 2019. 8. 19. BOJ 10265 - MT (sAdj, 위상정렬, knapsack) https://www.acmicpc.net/problem/10265 10265번: MT 문제 남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다. 재혁: 동우가 안 가면 나도 안 간다. 동우: 세종이가 안 가면 난 안 갈래. 버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 www.acmicpc.net 간선을 다음과 같이 잡아준다. u : 난 v없으면 안가 // v->u scc끼리 묶은 그래프를 보면, 한 컴포넌트씩 살펴봤을 때 ind가 .. 2019. 8. 19. 이전 1 2 3 다음
