結果

問題 No.177 制作進行の宮森あおいです！
ユーザー roarisroaris
提出日時 2020-11-28 03:39:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 279 ms / 2,000 ms
コード長 1,698 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 86,616 KB
実行使用メモリ 80,568 KB
最終ジャッジ日時 2023-10-09 23:25:32
合計ジャッジ時間 3,774 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
71,404 KB
testcase_01 AC 86 ms
71,336 KB
testcase_02 AC 83 ms
71,256 KB
testcase_03 AC 134 ms
77,000 KB
testcase_04 AC 113 ms
77,420 KB
testcase_05 AC 130 ms
78,688 KB
testcase_06 AC 174 ms
79,428 KB
testcase_07 AC 87 ms
71,460 KB
testcase_08 AC 113 ms
77,320 KB
testcase_09 AC 229 ms
79,716 KB
testcase_10 AC 279 ms
80,568 KB
testcase_11 AC 258 ms
79,956 KB
testcase_12 AC 216 ms
79,276 KB
testcase_13 AC 86 ms
71,560 KB
testcase_14 AC 87 ms
71,460 KB
testcase_15 AC 87 ms
71,200 KB
権限があれば一括ダウンロードができます

ソースコード

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