package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var w int fmt.Fscan(in, &w) var n int fmt.Fscan(in, &n) A := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &A[i]) } var m int fmt.Fscan(in, &m) B := make([]int, m) for i := 0; i < m; i++ { fmt.Fscan(in, &B[i]) } ok := make([][]bool, m) for i := 0; i < m; i++ { ok[i] = make([]bool, n) for j := 0; j < n; j++ { ok[i][j] = true } } for i := 0; i < m; i++ { var q int fmt.Fscan(in, &q) for j := 0; j < q; j++ { var x int fmt.Fscan(in, &x) ok[i][x-1] = false } } res := 制作進行の宮森あおいです(w, A, B, ok) if res { fmt.Fprintln(out, "SHIROBAKO") } else { fmt.Fprintln(out, "BANSAKUTSUKITA") } } func 制作進行の宮森あおいです(w int, A, B []int, ok [][]bool) bool { n, m := len(A), len(B) S, T := n+m, n+m+1 flow := NewDinic(n + m + 2) left := func(i int) int { return i } right := func(i int) int { return i + n } for i := 0; i < n; i++ { flow.AddEdge(S, left(i), A[i]) } for i := 0; i < m; i++ { flow.AddEdge(right(i), T, B[i]) } for j := 0; j < m; j++ { for i := 0; i < n; i++ { if ok[j][i] { flow.AddEdge(left(i), right(j), INF) } } } fmt.Println(ok) return flow.MaxFlow(S, T) >= w } const INF int = 1e18 type DinicEdge struct { to int cap int // 剩余容量 rev int // 逆向边在 G[to] 中的序号 isRev bool index int } type Dinic struct { graph [][]DinicEdge minCost []int iter []int } func NewDinic(n int) *Dinic { return &Dinic{ graph: make([][]DinicEdge, n), } } func (d *Dinic) AddEdge(from, to, cap int) { d.AddEdgeWithIndex(from, to, cap, -1) } func (d *Dinic) AddEdgeWithIndex(from, to, cap, index int) { d.graph[from] = append(d.graph[from], DinicEdge{to, cap, len(d.graph[to]), false, index}) d.graph[to] = append(d.graph[to], DinicEdge{from, 0, len(d.graph[from]) - 1, true, index}) } func (d *Dinic) MaxFlow(s, t int) int { flow := 0 for d.buildAugmentingPath(s, t) { d.iter = make([]int, len(d.graph)) f := 0 for { f = d.findMinDistAugmentPath(s, t, INF) if f == 0 { break } flow += f } } return flow } // (from,to,流量,容量) func (d *Dinic) GetEdges() [][4]int { res := make([][4]int, 0) for i, edges := range d.graph { for _, e := range edges { if e.isRev { continue } revEdge := d.graph[e.to][e.rev] res = append(res, [4]int{i, e.to, revEdge.cap, e.cap + revEdge.cap}) } } return res } func (d *Dinic) findMinDistAugmentPath(idx, t, flow int) int { if idx == t { return flow } i := d.iter[idx] for i < len(d.graph[idx]) { e := d.graph[idx][i] if e.cap > 0 && d.minCost[idx] < d.minCost[e.to] { f := d.findMinDistAugmentPath(e.to, t, min(flow, e.cap)) if f > 0 { d.graph[idx][i].cap -= f d.graph[e.to][e.rev].cap += f return f } } i++ d.iter[idx]++ } return 0 } func (d *Dinic) buildAugmentingPath(s, t int) bool { d.minCost = make([]int, len(d.graph)) for i := range d.minCost { d.minCost[i] = -1 } d.minCost[s] = 0 queue := []int{s} for len(queue) > 0 { v := queue[0] queue = queue[1:] for _, e := range d.graph[v] { if e.cap > 0 && d.minCost[e.to] == -1 { d.minCost[e.to] = d.minCost[v] + 1 queue = append(queue, e.to) } } } return d.minCost[t] != -1 } func min(a, b int) int { if a < b { return a } return b }