087 - Chokudai's Demand（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_ci

問題解説

N頂点あるグラフで、ある頂点からある頂点への移動コストが未確定の箇所がある。未確定の移動コストをXと決めたとき、任意のi, j間への移動コストがP以下になるような組み合わせがちょうどK個になるようなXの選び方はいくつあるか？

解き方

各頂点間の最小移動コストはワーシャルフロイド法で分かる
Xを何にするかを二分探索で求める
- なんで二分探索でいいかが分からない。広義単調減少列になると書いてあったが...

(ワーシャルフロイドを盆栽できたので良しとしたい)

var n, p, k int
var a [][]int

func solve() {
    in := getInts()
    n, p, k = in[0], in[1], in[2]

    a = make([][]int, n)
    for i := 0; i < n; i++ {
        a[i] = getInts()
    }

    l := getBoundary(k)
    r := getBoundary(k - 1)
    if r - l >= 2000000000 {
        fmt.Println("Infinity")
    } else {
        fmt.Println(r - l)
    }
}

func getBoundary(cnt int) int {
    left := 1
    right := 5000000000
    minx := right

    for i := 0; i < 40; i++ {
        mid := (left + right) / 2
        tmp := count(mid)
        if tmp <= cnt {
            right = mid
            minx = min(minx, mid)
        } else {
            left = mid
        }
    }
    return minx
}

func count(x int) int {
    graph := make([][]int, n)
    for i := 0; i < n; i++ {
        graph[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if a[i][j] == -1 {
                graph[i][j] = x
            } else {
                graph[i][j] = a[i][j]
            }
        }
    }

    dist := floydWarshall(graph)
    cnt := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if dist[i][j] <= p {
                cnt++
            }
        }
    }
    return cnt
}

func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            if i == j {
                dist[i][j] = 0
            } else if graph[i][j] == 0 {
                dist[i][j] = math.MaxInt64
            } else {
                dist[i][j] = graph[i][j]
            }
        }
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != math.MaxInt64 && dist[k][j] != math.MaxInt64 && dist[i][j] > dist[i][k]+dist[k][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    return dist
}

https://atcoder.jp/contests/typical90/submissions/54464105

hxrxchang / atcoder

087 - Chokudai's Demand（★5） #65

問題解説

解き方