만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 13161 분단의 슬픔

23 Jun 2021

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

n 명의 사람이 A진영과 B진영으로 나뉘어 들어갈 때 각 사람이 서로 다른 진영에 들어갈 때 슬픔 정도 w가 주어진다고 하자. 슬픔 정도의 합이 최소가 되도록 사람들을 A진영과 B진영으로 나누는 방법을 구하는 문제이다. 문제를 풀기전에 다음 이론 하나만 보고 가자.

1. Max Flow Min Cut

그래프의 선분들을 잘라내어 정점들을 2개의 서로 다른 집합으로 나누는 방법 중 가중치의 합이 최소일 때를 min cut이라고 하면 그 값은 max flow와 같다.

생각해보면 min cut에 포함된 간선들을 따라서 유량이 흐른다고 했을 때 min cut의 값은 간선들의 capacity의 합과 같다. 모든 유량은 결국 min cut에 포함된 간선들의 capacity합을 넘을 수 없게 된다. 따라서 해당 그래프의 최대 유량은 min cut과 같은 값을 갖게 되는 것이다.

2. 문제 풀이

다시 문제로 돌아와서 우리는 A진영에 속한 사람과 B진영에 속한 사람들의 슬픔 정도의 합의 최소를 찾고싶다. 모든 사람들을 하나의 정점으로 보고 서로간의 슬픔 정도를 capacity로 갖는 간선을 그린다고 하자. 이 경우 최대 유량을 구하면 capacity의 최소컷을 구할 수 있게 되고 이는 사람들을 A진영과 B진영으로 나누는 슬픔정도의 합과 같게 된다.

source와 sink는 어떻게 처리해야 할지에 대해 고민이 될 수 있다. 만약 A진영에 속한 사람과 source간에 capacity를 INF로 주고 B진영에 속한 사람과 sink간에 capacity를 INF로 준다고 하자. 그러면 A진영에 속해야 하는 사람은 INF를 min cut에 포함시킬 순 없기 때문에 무조건 A진영에 속하게 되고 B진영에 속해야 하는 사람은 무조건 B진영에 속할 수 있게 된다.

모든 V간에 edge가 연결되어 있는 형태이기 때문에 E의 갯수가 굉장히 크게 된다. 따라서 edmond 알고리즘을 쓰면 시간 초과가 나타나서 dinic 알고리즘을 활용하였다.

파일의 입력이 크기때문에 fread를 해줘야 시간초과가 안난다. 관련 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였다.
<출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>

/*
 fread 코드는 JCSooHwanCho님의 FileIO.swift 를 참조하였습니다.
 <출처 : https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88>
*/
import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

let fIO = FileIO()
let n = fIO.readInt()
let INF = 1_000_000_007
let s = 501, e = 502
var level:[Int] = Array(repeating: -1, count: 555)
var edge:[[Int]] = Array(repeating: [], count: 555)
var c:[[Int]] = Array(repeating: Array(repeating: 0, count: 555), count: 555)
var f:[[Int]] = Array(repeating: Array(repeating: 0, count: 555), count: 555)
var work:[Int] = Array(repeating: 0, count: 555)

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

func bfs() -> Bool {
    level = Array(repeating: -1, count: 555)
    var q = [Int]()
    level[s] = 1
    q.append(s)
    while !q.isEmpty {
        let curr = q.removeFirst()
        for i in edge[curr] {
            if level[i] == -1 && c[curr][i] - f[curr][i] > 0 {
                level[i] = level[curr] + 1
                q.append(i)
            }
        }
    }
    return level[e] != -1
}

func dfs(curr: Int, flow: Int) -> Int {
    if curr == e {
        return flow
    }
    let nextVertex = work[curr]
    for i in nextVertex..<edge[curr].count {
        let next = edge[curr][i]
        if level[next] == level[curr] + 1 && c[curr][next] - f[curr][next] > 0 {
            let tmp = dfs(curr: next, flow: min(flow, c[curr][next] - f[curr][next]))
            if tmp > 0 {
                f[curr][next] += tmp
                f[next][curr] -= tmp
                return tmp
            }
        }
        work[curr] += 1
    }
    return 0
}

func dinic() -> Int {
    var totalFlow = 0
    while bfs() {
        work = Array(repeating: 0, count: 555)
        while true {
            let tmpflow  = dfs(curr: s, flow: INF)
            if tmpflow == 0 {
                break
            }
            totalFlow += tmpflow
        }
    }
    return totalFlow
}

for i in 1...n {
    let v = fIO.readInt()
    if v == 1 {
        addEdge(s: s, e: i, val: INF)
    }
    else if v == 2 {
        addEdge(s: i, e: e, val: INF)
    }
}
for i in 1...n {
    for j in 1...n {
        let w = fIO.readInt()
        if i == j {
            continue
        }
        addEdge(s: i, e: j, val: w)
    }
}

print(dinic())
var a = "", b = ""
for i in 1...n {
    if level[i] != -1 {
        a += "\(i) "
    }
    else {
        b += "\(i) "
    }
}
print(a)
print(b)

Related posts