結果

問題 No.177 制作進行の宮森あおいです！
ユーザー Yuki_UtaaiYuki_Utaai
提出日時 2018-03-18 22:06:20
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 3,450 bytes
コンパイル時間 100 ms
コンパイル使用メモリ 11,200 KB
実行使用メモリ 9,484 KB
最終ジャッジ日時 2023-08-28 18:24:39
合計ジャッジ時間 1,171 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,768 KB
testcase_01 AC 18 ms
8,852 KB
testcase_02 AC 23 ms
8,752 KB
testcase_03 AC 21 ms
8,848 KB
testcase_04 AC 20 ms
9,040 KB
testcase_05 AC 22 ms
8,976 KB
testcase_06 AC 22 ms
9,112 KB
testcase_07 AC 18 ms
8,964 KB
testcase_08 AC 20 ms
9,072 KB
testcase_09 AC 25 ms
9,312 KB
testcase_10 AC 25 ms
9,396 KB
testcase_11 AC 24 ms
9,332 KB
testcase_12 AC 25 ms
9,484 KB
testcase_13 AC 19 ms
8,916 KB
testcase_14 AC 18 ms
8,760 KB
testcase_15 AC 17 ms
8,800 KB
権限があれば一括ダウンロードができます

ソースコード

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