E - Clique Connect

キーワード

解説

クラスカル法を考えると、辺の重みが小さい順に辺を追加していくと、最小全域木が得られる。

辺を追加する時も、閉路ができないように追加するため、 $\{A_{j,1}, A_{j,2}, \dots, A_{i,k_i}\}$ の全ての二点間に辺を張る必要はなく、 $A_{i,1}$ と $A_{i,j} \quad j = 2,3,\dots,k_i$ の間に辺を張るだけで十分。

提出コード

UnionFind はこちらから。

type Clique struct {
	k int
	c int
	a []int
}
 
func main() {
	var n, m int
	scanIntVariables(&n, &m)
	G := make([][][2]int, n+1)
	for i := 1; i <= n; i++ {
		G[i] = make([][2]int, 0)
	}
	uf := newUnionFind(n)
	Clique := make([]Clique, m)
	for i := 0; i < m; i++ {
		scanIntVariables(&Clique[i].k, &Clique[i].c)
		A := readInts()
		Clique[i].a = make([]int, Clique[i].k)
		for j := 0; j < Clique[i].k; j++ {
			Clique[i].a[j] = A[j] - 1
		}
	}
	sort.Slice(Clique, func(i, j int) bool {
		return Clique[i].c < Clique[j].c
	})
	ans := 0
	for i := 0; i < m; i++ {
		k, c, A := Clique[i].k, Clique[i].c, Clique[i].a
		for j := 1; j < k; j++ {
			if uf.isSame(A[0], A[j]) {
				continue
			}
			uf.unite(A[0], A[j])
			ans += c
		}
		if uf.size(1) == n {
			writeLine(ans)
			return
		}
	}
	writeLine(-1)
}

D - Permutation Subsequence 354