백준 11378 열혈강호 4
23 Jun 2021https://www.acmicpc.net/problem/11378
열혈강호 문제의 확장판으로 K라는 벌점이 주어지는데 이만큼 직원들이 추가로 일을 해낼 수 있다. 이분 매칭에서만보다가 네트워크 플로우로 적용시키려니 난감할 수 있지만 K라는 벌점을 부과해주는 새로운 정점을 하나 생성한다. 만약 해당 정점과 모든 사람들의 정점을 각각 K capacity를 갖는 edge로 연결해주면 손쉽게 구할 수 있다.
단 source에서 K 정점으로도 K capacity를 갖는 edge로 연결해주어 모든 사람들이 추가로 하는 일의 양이 K를 넘지 않도록 해준다.
그 외에는 source와 사람간에는 1 capacity로 사람과 일에도 1capacity로 일과 sink간에 1 capacity로 연결해준 뒤 최대 유량을 구해주면 된다. 앞에서 배운 에드몬드 카프 알고리즘을 활용했다.
- 전체 코드
let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0], m = nmk[1], k = nmk[2]
let s = 0, bridge = n+m+1, e = n+m+2
var c:[[Int]] = Array(repeating: Array(repeating: 0, count: e+1), count: e+1)
var f:[[Int]] = Array(repeating: Array(repeating: 0, count: e+1), count: e+1)
var edge:[[Int]] = Array(repeating: [], count: e+1)
// 0이 스타트 n+m+1이 bridge n+m+2가 end
for i in 1...n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
for j in 0..<line[0] {
let mIdx = n+line[j+1]
addEdge(s: i, e: mIdx, val: 1)
}
addEdge(s: s, e: i, val: 1)
addEdge(s: bridge, e: i, val: k)
}
addEdge(s: s, e: bridge, val: k)
for i in n+1...n+m {
addEdge(s: i, e: e, val: 1)
}
print(edward(s: s, e: e))
func addEdge(s: Int, e: Int, val: Int) {
edge[s].append(e)
edge[e].append(s)
c[s][e] += val
}
func edward(s: Int, e: Int) -> Int {
var result = 0
while true {
var parent:[Int] = Array(repeating: -1, count: e+1)
var q:[Int] = []
parent[s] = s
q.append(s)
while !q.isEmpty && parent[e] == -1 {
let curr = q.removeFirst()
for i in edge[curr] {
if c[curr][i] - f[curr][i] > 0 && parent[i] == -1 {
parent[i] = curr
q.append(i)
}
}
}
if parent[e] == -1 {
break
}
var idx = e
var minF = 1_000_000_000
while idx != s {
let prev = parent[idx]
minF = min(minF, c[prev][idx] - f[prev][idx])
idx = prev
}
idx = e
while idx != s {
let prev = parent[idx]
f[prev][idx] += minF
f[idx][prev] -= minF
idx = prev
}
result += minF
}
return result
}