https://www.acmicpc.net/problem/11408열혈강호 시리즈 다섯번째 문제입니다.이번 문제 또한 최대 유량 문제이지만 그 중에서 최소 코스트를 구하는 최소 비용 최대 유량(MCMF) 문제 입니다. 거창한 이름과는 다르게 해결 방법은 크게 새롭지 않습니다. 최대 유량 문제에서 길을 탐색할 때 모든 엣지의 코스트가 1 이었기 때문에 BFS 를 사용해 단순히 경로만 파악했다면 코스트가 생겼기 때문에 최단 코스트가 발생하는 경로를 찾아주면 됩니다. 최단 경로를 구한다면 가장 간단하게 다익스트라 알고리즘을 생각할 수 있지만 최대 유량 문제에서 코스트를 계산할 때에는 음의 경로로 이동할 경우 음의 코스트를 더해주어야 하기 때문에 다익스트라는 사용할 수 없습니다. 때문에 음의 경로가 존재해도 경..