목록2025/08/04 (1)
Elevation
그래프 (9) - 최소 비용 최대 유량
MCMF최대 유량(플로우)의 심화 버전인 최소 비용 최대 유량 문제(Min-cost Max-flow, MCMF)에 대해 알아보자. 말 그대로 최대 유량을 흘리되, 사용하는 간선의 비용 합이 최소가 되도록 하는 문제이다. 최대 유량과 마찬가지로 이용 가능한(즉, $capacity - flow > 0$) 간선으로 이루어진 경로를 찾고, 흘릴 수 있는 최대 유량 $f$를 구하여, 정방향으로 유량 $f$를 흘리고 역방향으로 $-f$를 흘리는 것은 동일하다. 정방향과 역방향이 모두 정의되는 유량 $flow$와 달리, 용량 $capacity$의 경우 source → sink의 단방향으로만 정의함에 주의하여 구현하는 것 역시 동일하다. 차이점은 최소 비용의 경로를 찾아야 하기 때문에, 경로 탐색에 단순 bfs/dfs..
ps/graph
2025. 8. 4. 00:46