/
1408E.go
55 lines (51 loc) · 971 Bytes
/
1408E.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package main
import (
"bufio"
. "fmt"
"io"
"sort"
)
// github.com/EndlessCheng/codeforces-go
func CF1408E(_r io.Reader, out io.Writer) {
in := bufio.NewReader(_r)
type edge struct{ v, w, wt int }
var m, n, k, w int
Fscan(in, &m, &n)
a := make([]int, m)
for i := range a {
Fscan(in, &a[i])
}
b := make([]int, n)
for i := range b {
Fscan(in, &b[i])
}
es := []edge{}
for i, v := range a {
for Fscan(in, &k); k > 0; k-- {
Fscan(in, &w)
es = append(es, edge{i, m + w - 1, v + b[w-1]})
}
}
sort.Slice(es, func(i, j int) bool { return es[i].wt > es[j].wt })
fa := make([]int, m+n)
for i := range fa {
fa[i] = i
}
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
ans := int64(0)
for _, e := range es {
if fv, fw := find(e.v), find(e.w); fv != fw {
fa[fv] = fw
} else {
ans += int64(e.wt)
}
}
Fprint(out, ans)
}
//func main() { CF1408E(os.Stdin, os.Stdout) }