티스토리 뷰
MCMF(Minimum-Cost Maximum-Flow)는 최소 비용 최대 유량이라고도 불리며
네트워크의 각 간선마다 유량을 1 흘려보낼 때 드는 비용이 정해져 있을 때
최대 유량을 어떻게 흘려보내야 비용의 합을 최소화 할 수 있는 지를 알아내는 방법입니다.
그래프파트에서 다뤘던 간선에 비용이 있는 그래프에서의 최단경로를 매번 찾은 뒤
이 경로로 흐를 수 있는 최대 유량을 찾아서 흘려보내면서
이전에 찾은 경로의 비용 합 * 유량을 반복하여 계속 더해주며 구합니다.
이 때의 최단 경로 알고리즘이 유량 그래프의 특성에 따라 음의 가중치가 있는 그래프에서도 가능하여야 하므로
앞서 배운 벨만 포드 알고리즘의 변형인 SPFA(Shortest Path Faster Algorithm)을 사용합니다.
SPFA의 시간복잡도는 벨만 포드와 동일한 O(VE)이지만 좀 더 빠르게 돌아가며 이 후 동작원리는 네트워크 유량과 동일합니다.
이에따라 MCMF의 시간복잡도는 O(VEf)입니다.
최대 비용 최대 유량을 구하고 싶을 경우에는 모든 간선에 -1을 곱한 뒤 동일한 과정을 진행하면 값을 알아낼 수 있으며
네트워크 유량에서의 테크닉 또한 많이 사용되는 문제 유형입니다.
기본 문제
3640번: 제독
댓글