Dev_Diary

https://www.acmicpc.net/problem/11405지난 문제와 같이 최소 비용 최대 유량 문제입니다.SPFA 알고리즘과 네트워크 플로우 알고리즘을 함께 사용해 풀었습니다.최대 비용을 구할 때 전달된 책의 수를 곱해주어야 합니다. import sysfrom collections import dequeinput = sys.stdin.readline# SPFAdef spfa(start, N, M, graph, flowable): # 방문 목록 visited = [-1 for _ in range(1+M+N+1)] visited[start] = start # 최단거리 min_dists = [float('inf') for _ in range(1+M+N+1)] min_..

https://www.acmicpc.net/problem/11408열혈강호 시리즈 다섯번째 문제입니다.이번 문제 또한 최대 유량 문제이지만 그 중에서 최소 코스트를 구하는 최소 비용 최대 유량(MCMF) 문제 입니다. 거창한 이름과는 다르게 해결 방법은 크게 새롭지 않습니다. 최대 유량 문제에서 길을 탐색할 때 모든 엣지의 코스트가 1 이었기 때문에 BFS 를 사용해 단순히 경로만 파악했다면 코스트가 생겼기 때문에 최단 코스트가 발생하는 경로를 찾아주면 됩니다. 최단 경로를 구한다면 가장 간단하게 다익스트라 알고리즘을 생각할 수 있지만 최대 유량 문제에서 코스트를 계산할 때에는 음의 경로로 이동할 경우 음의 코스트를 더해주어야 하기 때문에 다익스트라는 사용할 수 없습니다. 때문에 음의 경로가 존재해도 경..