AtCoder CODE FESTIVAL 2016 qual B C - Gr-idian MST (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。少し時間が取れなかったので月曜から過去問です。

問題

最小全域木を生成するアルゴリズムに貪欲法の要素を加えた感じになります。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 1000000000

type key struct {
    cost int
    open int
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m := nextInt(), nextInt()
    pattern := 1 << uint(n)
    keys := make([]key, m)
    for mi := 0; mi < m; mi++ {
        a, b := nextInt(), nextInt()
        open := 0
        for bi := 0; bi < b; bi++ {
            c := nextInt()
            open = open | (1 << uint(c-1))
        }
        keys[mi] = key{a, open}
    }

    dp := make([][]int, m+1)
    dp[0] = make([]int, pattern)
    // dp[0][0] = 0
    for pi := 1; pi < pattern; pi++ {
        dp[0][pi] = INF
    }

    for mi := 0; mi < m; mi++ {
        dp[mi+1] = make([]int, pattern)
        copy(dp[mi+1], dp[mi])
        for pi := 0; pi < pattern; pi++ {
            pnext := pi | keys[mi].open
            if dp[mi][pi]+keys[mi].cost < dp[mi+1][pnext] {
                dp[mi+1][pnext] = dp[mi][pi] + keys[mi].cost
            }
        }
    }

    switch {
    case dp[m][pattern-1] < INF:
        fmt.Println(dp[m][pattern-1])
    default:
        fmt.Println(-1)
    }
}

最小全域木を求めるアルゴリズムとしてはクラスカル法が有名ですが、クラスカル法の計算量は辺の数を $E$ とすると $O(E\log E)$ です。一方で辺の数は $O(WH)$ であるため、クラスカル法をそのまま用いると計算が間に合いません。

そこでクラスカル法がどういうアルゴリズムかを見直してみます。

各頂点を頂点1の木とおく。
全ての辺の集合から長さの最も短い辺を取り出す。
取り出した辺が2つの木を結ぶ場合、それらをまとめて1つの木にする。
2.と3.を繰り返すと最終的に1つの最小全域木が残る。

今回の問題では、（端点の） $x$ 座標または $y$ 座標が同じ辺の集合は長さが同じなので、そういった辺の集合ごとに考えればよさそうです。具体的には次のようなアルゴリズムで解くことができます。

$x$ 座標または $y$ 座標が同じ辺の集合をそれぞれ作る。
辺の集合の集合から、辺の長さ（コスト）の最も短い辺の集合を取り出す。
1. そのような集合が複数ある場合は、その中の1つを取り出す（まとめて取り出さない）。
取り出した辺の集合が軸に平行なら、辺の本数から軸に平行で既に取り出したことのある辺の集合の数を引き、その数の辺を求める最小全域木に加える。
1. $y$ 軸に平行な辺の集合についても同様。
2.と3.を繰り返すと最終的に最小全域木の辺の長さ（コスト）の合計が求められる。

このアルゴリズムで解が求められることを簡単な例で示します。 $H,W=1,p_0=1,q_0=2$ の場合を考えると、以下の流れで解くことができます。