백준 14750 Jerry and Tom
23 Jun 2021https://www.acmicpc.net/problem/14750
집의 코너 수 n, 각 구멍마다 쥐를 숨길 수 있는 마리 수 k, 구멍의 수 h, 쥐의 수 m이 주어지고 이어서 코너 정보와 구멍 위치와 쥐의 위치가 주어진다고 하자. 쥐는 눈에 보이는 구멍에만 숨을 수 있다고 했을 때 모든 쥐를 숨길 수 있는지 여부를 나타내는 문제이다.
핵심이 되는 네트워크 플로우 알고리즘은 기존 것을 사용하면 되는데 edge와 capacity 설정이 어려운 문제이다. 일단 각각의 쥐들과 구멍들을 하나의 정점으로 보자. 모든 구멍은 source와 k만큼의 capacity를 갖도록 연결시키고 구멍에서 쥐로 1의 capacity를 갖는 edge로 연결시키자. 마지막으로 쥐와 sink간에는 1의 capacity를 갖는 edge로 연결한다고 하자.
이렇게 되면 source부터 sink까지 최대 유량이 m이 나오게 되면 모든 쥐를 통해 flow가 1씩 흐른다는 소리이므로 구멍에 쥐들을 숨기는 것이 가능하다는 의미가 된다. 따라서 에드몬드 알고리즘을 활용해서 구현이 가능하다.
- Edge&Capacity Set Code
for i in 0..<h {
for j in 0..<m {
if !crash(hole: hole[i], mouse: mouse[j]) {
makeEdge(s: i+1, e: h+j+1, val: 1)
}
}
makeEdge(s: s, e: i+1, val: k)
}
for i in h+1...h+m {
makeEdge(s: i, e: e, val: 1)
}
단 유의할 것은 쥐의 좌표와 구멍의 좌표가 주어졌을 때 둘이 벽에 의해 가로막히지 않을 경우에만 edge를 연결시켜준다는 것이다. 따라서 기하학적인 함수들이 사용되는데 선분간의 만남 여부를 확인해주는 파트는 공부를 하고 보는 것을 추천드린다.
쥐와 구멍의 좌표가 하나씩 주어지면 집의 모든 벽에 대해서 쥐와 구멍을 이은 선분과 모든 벽 선분이 만나는 적이 있는지 확인해주고 만난다면 쥐가 구멍을 볼 수 없다는 뜻이므로 edge 추가를 해주지 않는다.
- 전체 코드
let nkhm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nkhm[0], k = nkhm[1], h = nkhm[2], m = nkhm[3]
var corner = Array(repeating: (0, 0), count: n)
var hole = Array(repeating: (0, 0), count: h)
var mouse = Array(repeating: (0, 0), count: m)
let s = 0, e = h+m+1
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)
for i in 0..<n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
corner[i] = (line[0], line[1])
}
for i in 0..<h {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
hole[i] = (line[0], line[1])
}
for i in 0..<m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
mouse[i] = (line[0], line[1])
}
for i in 0..<h {
for j in 0..<m {
if !crash(hole: hole[i], mouse: mouse[j]) {
makeEdge(s: i+1, e: h+j+1, val: 1)
}
}
makeEdge(s: s, e: i+1, val: k)
}
for i in h+1...h+m {
makeEdge(s: i, e: e, val: 1)
}
if edward(s: 0, e: e) == m {
print("Possible")
}
else {
print("Impossible")
}
func makeEdge(s: Int, e: Int, val: Int) {
edge[s].append(e)
edge[e].append(s)
c[s][e] += val
}
func ccw(a: (Int, Int), b: (Int, Int), c: (Int, Int)) -> Int {
let result:CLongLong = CLongLong(b.0-a.0)*CLongLong(c.1-a.1) - CLongLong(b.1-a.1)*CLongLong(c.0-a.0)
return result > 0 ? 1 : (result == 0 ? 0 : -1)
}
func meet(a1: (Int, Int), a2: (Int, Int), b1: (Int, Int), b2: (Int, Int)) -> Bool {
let ccw1 = ccw(a: a1, b: a2, c: b1)
let ccw2 = ccw(a: a1, b: a2, c: b2)
let ccw3 = ccw(a: b1, b: b2, c: a1)
let ccw4 = ccw(a: b1, b: b2, c: a2)
if ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0 {
var A = a1, B = a2, C = b1, D = b2
if A > B {
swap(&A, &B)
}
if C > D {
swap(&C, &D)
}
return C <= B && A <= D
}
return ccw1*ccw2 <= 0 && ccw3*ccw4 <= 0
}
func crash(hole: (Int, Int), mouse: (Int, Int)) -> Bool {
for i in 0..<n {
let j = (i+1)%n
if hole.0 == corner[i].0 && hole.0 == corner[j].0 {
continue
}
if hole.1 == corner[i].1 && hole.1 == corner[j].1 {
continue
}
if meet(a1: hole, a2: mouse, b1: corner[i], b2: corner[j]) {
return true
}
}
return false
}
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)
loop: while !q.isEmpty {
let curr = q.removeFirst()
for next in edge[curr] {
if c[curr][next]-f[curr][next] > 0 && parent[next] == -1 {
parent[next] = curr
q.append(next)
if next == e {
break loop
}
}
}
}
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
}