백준 11376 열혈강호 2
23 Jun 2021https://www.acmicpc.net/problem/11376
N명의 직원이 있고 M개의 일이 있다고 했을 때 각 직원별로 최대 2개의 일을 할 수 있다고 하자. 해낼 수 있는 최대 일의 갯수를 구하는 문제이다. 전형적인 이분매칭의 문제로 열혈강호 1에서 새로운 규칙 하나가 추가된 문제이다.
어려워 보일수도 있지만 사람의 수를 2배로 만들어 버리면 되는 간단한 문제이다. 이 후 최대 매칭의 갯수를 구해주면 된다.
- 전체 코드
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var work:[[Int]] = []
var visited:[Bool] = Array(repeating: false, count: m+1)
var work2Worker:[Int] = Array(repeating: -1, count: m+1)
var maxWork = 0
func dfs(worker: Int) -> Bool {
let workCount = work[worker][0]
for i in 1..<workCount+1 {
let currWork = work[worker][i]
if visited[currWork] {
continue
}
visited[currWork] = true
if work2Worker[currWork] == -1 || dfs(worker: work2Worker[currWork]) {
work2Worker[currWork] = worker
return true
}
}
return false
}
for i in 0..<n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
work.append(line)
work.append(line)
visited = Array(repeating: false, count: m+1)
if dfs(worker: 2*i) {
maxWork += 1
}
visited = Array(repeating: false, count: m+1)
if dfs(worker: 2*i+1) {
maxWork += 1
}
}
print(maxWork)