WonYong-Jang / algorithm

0 stars 0 forks source link

MCMF (Minimum Cost Maximum Flow) #30

Open WonYong-Jang opened 5 years ago

WonYong-Jang commented 5 years ago

MCMF

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

11408 열혈강호 5

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