結果

問題 No.177 制作進行の宮森あおいです！
ユーザー roaris
提出日時 2020-11-28 03:39:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 1,698 bytes
コンパイル時間 742 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 77,996 KB
最終ジャッジ日時 2024-09-12 21:54:14
合計ジャッジ時間 3,202 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

class FordFulkerson:
    def __init__(self, N, edges): #edges: (s, t, c) sからtに向かう容量cの有向辺
        self.N = N
        self.G = defaultdict(lambda : defaultdict(int))
        
        for s, t, cap in edges:
            self.G[s][t] = cap
        
    def dfs(self, v, t, f):
        if v==t:
            return f
        
        self.used[v] = True
        
        for nv, cap in self.G[v].items():
            if not self.used[nv] and self.G[v][nv]>0:
                d = self.dfs(nv, t, min(f, self.G[v][nv]))
                
                if d>0:
                    self.G[v][nv] -= d
                    self.G[nv][v] += d
                    
                    return d
        
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        
        while True:
            self.used = [False]*self.N
            f = self.dfs(s, t, 10**18)
        
            if f==0:
                return flow
        
            flow += f

W = int(input())
N = int(input())
J = list(map(int, input().split()))
M = int(input())
C = list(map(int, input().split()))
out = [[False]*M for _ in range(N)]

for i in range(M):
    QX = list(map(int, input().split()))
    Q = QX[0]
    
    for j in range(Q):
        out[QX[j+1]-1][i] = True

edges = []

for i in range(N):
    edges.append((0, i+1, J[i]))

for i in range(N):
    for j in range(M):
        if not out[i][j]:
            edges.append((i+1, N+j+1, J[i]))

for i in range(M):
    edges.append((N+i+1, N+M+1, C[i]))

ff = FordFulkerson(N+M+2, edges)

if ff.max_flow(0, N+M+1)>=W:
    print('SHIROBAKO')
else:
    print('BANSAKUTSUKITA')
0