oVeron

1.\(N\)명의 사람들이 벌점 \(K\)에 따라 \(M\)개의 일들을 최대로 하도록 하는 문제이다. 한 사람이 하는 일의 개수를 유량이라 한다면, \(N\)명의 사람들과 \(M\)명의 일들을 그래프로 표현해 최대 유량을 구하면 된다. 따라서 이 문제는 최대 유량 문제이다. 2.먼저 \(N\)명의 사람들과 \(M\)명의 일들을 그래프로 표현할 때, 한 사람이 여러 일을 할 수는 없으므로 간선들의 용량은 전부 \(1\)이 된다. 각 노드들을 \(source, sink\)와 연결시킨 간선들의 용량 역시 전부 \(1\)일 것이다.벌점 \(K\)에 대한 처리는 \(source\)와 용량 \(K\)로 연결된 노드 \(A\)를 하나 만들어서, 노드 \(A\)를 \(N\)명의 사람들과 연결시키면 된다. 이때 노드 \..

알고리즘/baekjoon 2024. 6. 29. 16:15