만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 11409 열혈강호 6

23 Jun 2021

https://www.acmicpc.net/problem/11409

열혈강호 문제의 6번째 확장판. MCMF에서는 그동안 최소 비용 최대 플로우를 구했다면 최대 비용 최대 플로우를 구하는 문제이다. 생각해보면 flow를 구하는 과정은 동일할 것이기 때문에 최소 비용이 아닌 최대 비용으로 경로를 구하는 것이 핵심이다. 따라서 SPFA 알고리즘을 다음과 같이 수정해야 한다.

while !queue.isEmpty {
    let curr = queue.removeFirst()
    inq[curr] = false
    for next in edge[curr] {
        if c[curr][next] - f[curr][next] <= 0 {
            continue
            // flow가 흐를 수 없는 경로는 continue
        }
        if dst[curr] < INF && (dst[next] == INF || dst[next] < dst[curr]+d[curr][next]) {
            dst[next] = dst[curr]+d[curr][next]
            parent[next] = curr
            if !inq[next] {
                queue.append(next)
                inq[next] = true
            }
        }
    }
}

그동안은 값이 작다면 업데이트를 시켜주고 queue에 집어넣었다면 이번에는 값이 클 경우에만 업데이트를 시켜주고 queue에 집어넣는 방식으로 구현했다. dst[next]에 값이 입력된 적이 없는 default 상태일 경우 예외처리를 해줘야 함을 확인하자. 나머지 코드는 열혈강호 5의 코드와 동일하게 MCMF 알고리즘을 그대로 동작시키면 된다.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
let s = 0, e = n+m+1, INF = 1_000_000_007
var c:[[Int]] = Array(repeating: Array(repeating: 0, count: n+m+2), count: n+m+2)
var f:[[Int]] = Array(repeating: Array(repeating: 0, count: n+m+2), count: n+m+2)
var d:[[Int]] = Array(repeating: Array(repeating: 0, count: n+m+2), count: n+m+2)
var edge:[[Int]] = Array(repeating: [], count: n+m+2)
var parent:[Int] = Array(repeating: -1, count: n+m+2)

func SPFA() -> Bool {
    var dst = Array(repeating: INF, count: n+m+2)
    var inq = Array(repeating: false, count: n+m+2)
    var queue = [Int]()
    queue.append(s)
    inq[s] = true
    dst[s] = 0
    while !queue.isEmpty {
        let curr = queue.removeFirst()
        inq[curr] = false
        for next in edge[curr] {
            if c[curr][next] - f[curr][next] <= 0 {
                continue
            }
            if dst[curr] < INF && (dst[next] == INF || dst[next] < dst[curr]+d[curr][next]) {
                dst[next] = dst[curr]+d[curr][next]
                parent[next] = curr
                if !inq[next] {
                    queue.append(next)
                    inq[next] = true
                }
            }
        }
    }
    return dst[e] != INF
}

func flow() -> (Int, Int) {
    var totalFlow = 0, money = 0
    while SPFA() {
        var idx = e, cost = 0, minF = INF
        while idx != s {
            let prev = parent[idx]
            minF = min(minF, c[prev][idx]-f[prev][idx])
            cost += d[prev][idx]
            idx = prev
        }
        idx = e
        while idx != s {
            let prev = parent[idx]
            f[prev][idx] += minF
            f[idx][prev] -= minF
            idx = prev
        }
        money += cost*minF
        totalFlow += minF
    }
    return (totalFlow, money)
}

func addEdge(s: Int, e: Int, val: Int) {
    edge[s].append(e)
    edge[e].append(s)
    c[s][e] += val
}

for i in 1...n {
    addEdge(s: s, e: i, val: 1)
    let line = readLine()!.split(separator: " ").map{Int(String($0))!}
    for j in 0..<line[0] {
        let workIdx = n+line[2*j+1], cost = line[2*j+2]
        addEdge(s: i, e: workIdx, val: 1)
        d[i][workIdx] = cost
        d[workIdx][i] = -cost
    }
}
for i in n+1...n+m {
    addEdge(s: i, e: e, val: 1)
}
let result = flow()
print(result.0)
print(result.1)

Related posts