MCMF (Minimum Cost Maximum Flow)

[WonYong-Jang]

MCMF

• 최소 비용을 구하여 그 최소 비용에 해당하는 간선으로 최대 유량을 구하는 문제
• 최소 비용이라 함은 최단 거리를 구하는 문제가 되고 이때, 최단 거리는 최단 거리알고리즘을
  쓰면 되지만, 이 문제에서는 비용이 음수가 될 수 있기에 벨만 포드 알고리즘을 써도 가능
  하지만 벨만포드 성능을 향상시킨 SPFA 알고리즘 이용
• SPFA 를 통한 최소 비용을 구하고 그때의 최대 유량을 구하면 되니 결과값은
  경로 비용의 합 * 유량

11408 열혈강호 5

• 대표적인 MCMF 문제
  출처 :
  http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220810623254
  https://www.crocus.co.kr/1090