백준 2316 도시 왕복하기 2
23 Jun 2021https://www.acmicpc.net/problem/2316
1번 도시와 2번 도시 사이를 왔다 가려는데 이 때 한번 방문한 도시는 두 번 이상 거치지 않으려고 한다고 한다. 1번 도시와 2번 도시를 왔다 갔다 하는 최대 횟수를 구하는 문제이다. 신기하게도 정점을 1번만 방문하도록 설정해줘야 하는 문제이다.
정점 분할 이라는 개념을 사용할 것인데 정점을 in과 out으로 분할하여 둘 사이의 용량을 1로 설정해주는 기법이다. 이렇게 되면 해당 정점은 1만큼의 flow를 흘릴 수 있기 때문에 최대 1번만 방문이 가능해진다. 이 때 양방향 간선인지 단방향 간선인지에 따라 정점 분할의 형태가 달라진다.
- 단방향 간선
- 양방향 간선
따라서 만약 A 도시에서 B 도시간에 양방향 길이 있다면 Aout과 Bin 간에 capacity 1을 설정해주고 Bout과 Ain 간에도 마찬가지로 설정해준다. 이 때 모든 도시 내부의 in 노드와 out 노드 간에도 1의 capacity를 부여해줘야한다. edge 설정이 끝났다면 1번 도시와 2번 도시 사이의 최대 유량을 구해주면 된다.
- 전체 코드
let np = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = np[0], p = np[1]
var c:[[Int]] = Array(repeating: Array(repeating: 0, count: 2*n+1), count: 2*n+1)
var f:[[Int]] = Array(repeating: Array(repeating: 0, count: 2*n+1), count: 2*n+1)
var edge:[[Int]] = Array(repeating: [], count: 2*n+1)
for _ in 0..<p {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
makeEdge(s: 2*line[0], e: 2*line[1]-1, val: 1)
makeEdge(s: 2*line[1], e: 2*line[0]-1, val: 1)
}
for i in 1...n {
edge[2*i-1].append(2*i)
c[2*i-1][2*i] = 1
}
print(edward(s: 2, e: 3))
func makeEdge(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: 2*n+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
}