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로..
https://www.acmicpc.net/problem/6086 주어진 파이프를 이용해 A -> Z 로의 최대 유량을 계산하는 문제입니다. 주의할 점 : 소문자도 된다. 병렬로 연결도 가능하다. 양방향 연결이다. Edmonds Karp 알고리즘을 이용해 최대 유량을 계산하면 되지만, 양방향성과 병렬 가능에 주의를 해야 합니다. 기본적으로는 가상의 역방향 엣지를 추가하고, cap은 0으로 유지하여 Edmonds-Karp 알고리즘을 수행하지만, 양방향이므로, 역방향 엣지와 cap을 동일하게 잡아줍니다. 그리고 병렬처리가 가능하므로 cap을 누적하여 추가해줍니다. 불필요한 bfs 탐색을 방지하기 위해 vector에 누적해서 동일한 node를 추가하는 것 대신, set으로 연결된 노드를 관리하였습니다. ..
참고 : 알고리즘 문제 해결 전략 - 구종만 최대 유량 문제 : 네트워크 상에서 엣지에 보낼 수 있는 용량이 정해져 있을 때, 어떻게 하면 source에서 sink로 최대로 유량을 보낼 수 있는가에 대한 문제 기본적인 최대 유량 문제 해결을 위한 알고리즘- Ford-Fulkerson, Edmonds-Karp, Dinic 알고리즘 Ford-Fulkerson : source에서 sink로 보낼 수 있는 최대 유량을 보낼 수 있는 경로를 계속 찾는 방식 (exponetial하든 polytime이든 상관없이 첫 아이디어 관점이지만, 대부분 이에 기초한 방식을 사용)Edmonds-Karp : Ford-Fulkerson 알고리즘에서 최대 유량 보낼 수 있는 경로를 bfs 기반으로 찾음 (bfs 기반으로 찾을 때 ..
https://www.acmicpc.net/problem/1219(SPFA 연습을 위해 벨만 포드로 풀 수 있는 문제 중 선택을 해보았다.) 민식이는 특정 시작점에서 도착점까지 가는 경로마다 비용이 있고, 노드에 도착하면 돈을 법니다. 문제를 다음과 같이 치환할 수 있습니다. a node -> b node 비용 cost, b node 도착 시 버는 돈 earn : a -> b 갔을 때 버는 금액 = earn - cost도착 지점에 도달했을 때 버는 최종 금액을 최대로 하도록 하여라. 시작점에서도 버는 금액이 포함되는 건지가 햇갈렸는데 test case 5번을 보면 포함됨을 알 수 있습니다. (7만큼 0번에서 번다, 0번에서 0번으로 갈 때는 10의 cost가 든다. => 답 7 => 처음 0번 시작할..