結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー Yuki_Utaai
提出日時 2018-03-18 22:06:20
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 3,450 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-12-30 03:03:39
合計ジャッジ時間 1,642 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2435165
#AOJ最大流プログラム
#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

import collections
class Dinic:

    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]

    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])

    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])

    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level

    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


#今回の問題分（インプット、頂点の組）FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

w=int(input())
n=int(input())
jj=[int(i) for i in input().split()]
m=int(input())
cc=[int(i) for i in input().split()]

qx=[]
for i in range(m):
    qx.append([int(i) for i in input().split()])
    del qx[i][0]
#    if qx[i]==[]:   

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


#頂点の組u,vと辺の重みc（今回は1）からグラフ作って最大流で解くFOOOOOOOOOOOO

V=n+m+2 #(sとt追加)

dinic = Dinic(V)

for i in range(n): #始点s（番号0）から原画マンへの辺
    u, v, c = 0, i+1, jj[i]
    dinic.add_edge(u, v, c)
            
for i in range(m): #　作画監督から終点t（番号V-1）への辺
    u, v, c = i+n+1, V-1, cc[i]
    dinic.add_edge(u, v, c)    
    
for i in range(n): #原画マンから作画監督への辺
    for j in range(m):

        if i+1 not in qx[j]: 
            node1, node2, omomi = i+1, j+n+1, 100000
        else:
            node1, node2, omomi = i+1, j+n+1, 0

        u, v, c = node1, node2, omomi
        dinic.add_edge(u, v, c)
        
#print (dinic.max_flow(0, V-1))     

if dinic.max_flow(0, V-1)>=w:
    print("SHIROBAKO")
else:
    print("BANSAKUTSUKITA")

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


"""
元々のinput
V, E =  [int(i) for i in input().split()]

dinic = Dinic(V)

for i in range(E):
    u, v, c = [int(i) for i in input().split()]
    dinic.add_edge(u, v, c)

print (dinic.max_flow(0, V-1))

"""
0