알고리즘/그래프
2020. 7. 14.
Minimum Cost Maximum Flow
만약 그래프의 간선에 비용과 용량이 모두 존재하면 어떨까요? 간선에 1의 용량을 흘릴 때마다 그 간선에 주어진 비용이 드는 그래프를 생각할 수 있습니다. 용량과 비용이 있는 방향그래프에서, 시작점 \(S\)에서 끝점 \(T\)까지 흐를 수 있는 최대 용량을 구하되, 그 때의 비용을 최소로 만드는 문제를 MCMF(Minimum Cost Maximum Flow) 문제라고 합니다. 예를 들어 다음과 같은 그래프에서, 최대 유량은 60, 그 때의 최소 비용은 210이고, 실해는 다음과 같습니다. https://www.acmicpc.net/problem/11408 11408번: 열혈강호 5 강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부..
