https://www.acmicpc.net/problem/11409 열혈강호 5와 마찬가지로 mcmf 알고리즘 문제입니다. mcmf 기본 설명 및 코드 : https://ghqls0210.tistory.com/377 백준 11408 열혈강호 5https://www.acmicpc.net/problem/11408 MCMF 알고리즘을 공부할 수 있는 문제였습니다. MCMF 알고리즘이란, 최소 비용으로 최대 유량을 보내도록 값을 찾는 알고리즘입니다. 즉, 엣지마다 비용이 정해져ghqls0210.tistory.com 단, 일반적인 mcmf와 달리, 최대 비용, 최대 유량을 구합니다. 이는 비용을 처음부터 음수로 처리하여 최소 비용 최대 유량을 구하는 것과 동일하게 계산하면, 음수 중 최소값이므로, 최종 계산 시..
https://www.acmicpc.net/problem/11408 MCMF 알고리즘을 공부할 수 있는 문제였습니다. MCMF 알고리즘이란, 최소 비용으로 최대 유량을 보내도록 값을 찾는 알고리즘입니다. 즉, 엣지마다 비용이 정해져 있다면, 최대 유량을 보내는 방법이 여러 가지일텐데, 그 중 가장 최소 비용 값을 찾는 것입니다. 전체 비용은 sum(엣지의 비용 * 엣지의 유량) 으로 계산됩니다. MCMF 알고리즘과 관련된 문제들은 edmonds-karp에 spfa를 적용하여 푸는 것으로 알려져 있습니다.즉, edmonds-karp로 최대 유량을 계산할 때, 단순히 증가 경로 상에 부모 노드를 고르는 것이 아닌, 최소 비용을 갖는 엣지를 통해 부모를 선택합니다. 이 때 최소 비용 경로 계산을 spfa로..