반응형 포드풀커슨1 백준 11378번 열혈강호 4 - C++(cpp) 풀이 1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다. 2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다. 3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다. 1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다. 2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다. 3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다. 포드 풀커슨 알고리즘의 시간 복잡도는 O((V + E) * F)... 2022. 3. 9. 이전 1 다음 반응형
