結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー fumuumuf
提出日時 2020-05-16 15:24:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,099 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 26,400 KB
最終ジャッジ日時 2024-09-22 09:26:22
合計ジャッジ時間 12,732 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 2 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(10 ** 9)

TO, CAP, REV = 0, 1, 2  # 行き先, 容量, 逆辺(相手方のリスト中のこちら向きの辺の index)
MAX_V = 10 ** 5 + 10
INF = 10 ** 12


class FordFulkerson:
    """
    最大流を求める
    ford-fulkerson のアルゴリズム
    """

    def __init__(self):
        self.G = [[] for _ in range(MAX_V)]
        self.used = [False] * MAX_V

    def add_edge(self, from_, to_, cap):
        self.G[from_].append([to_, cap, len(self.G[to_])])
        self.G[to_].append([from_, 0, len(self.G[from_]) - 1])

    def dfs(self, v, t, f):
        """
        増加パスを探す
        v: 現在の v
        t: target v
        f: 流入量
        """
        if v == t: return f

        self.used[v] = True
        for i, e in enumerate(self.G[v]):
            if not self.used[e[TO]] and e[CAP] > 0:
                d = self.dfs(e[TO], t, min(f, e[CAP]))  # e[TO] を利用して, 流せる capacity
                if d > 0:
                    e[CAP] -= d
                    rev_e = self.G[e[TO]][e[REV]]
                    rev_e[CAP] += d  # 逆辺の CAP +d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while 1:
            for i in range(MAX_V): self.used[i] = False
            f = self.dfs(s, t, INF)
            if f == 0: return flow
            flow += f


def main():
    W = int(input())
    N = int(input())

    g = FordFulkerson()
    J = [int(_) for _ in input().split()]

    for j in range(N):
        g.add_edge(0, j + 1, J[j])

    M = int(input())
    C = [int(_) for _ in input().split()]

    TO = N + M + 10
    CS = N + 1
    for c in range(M):
        g.add_edge(CS + c + 1, TO, C[c])

    for i in range(1, M + 1):
        vidx = CS + i
        x = {int(_) for _ in input().split()[:1]}
        for j in range(1, N + 1):
            if j not in x:
                g.add_edge(j, vidx, J[j - 1])

    res = g.max_flow(0, TO)
    if res >= W:
        print('SHIROBAKO')
    else:
        print('BANSAKUTSUKITA')


if __name__ == '__main__':
    main()
0