結果

問題 No.177 制作進行の宮森あおいです！
ユーザー roiti46roiti46
提出日時 2015-05-28 03:57:17
言語 Python2
(2.7.18)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 2,342 bytes
コンパイル時間 541 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-07-06 12:05:21
合計ジャッジ時間 1,432 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
6,812 KB
testcase_01 AC 10 ms
6,944 KB
testcase_02 AC 10 ms
6,940 KB
testcase_03 AC 11 ms
6,940 KB
testcase_04 AC 11 ms
6,944 KB
testcase_05 AC 13 ms
6,944 KB
testcase_06 AC 15 ms
6,940 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 12 ms
7,040 KB
testcase_09 AC 16 ms
7,552 KB
testcase_10 AC 17 ms
7,424 KB
testcase_11 AC 16 ms
7,424 KB
testcase_12 AC 16 ms
7,424 KB
testcase_13 AC 12 ms
6,940 KB
testcase_14 AC 12 ms
6,944 KB
testcase_15 AC 12 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import namedtuple

class MaxFlowDinic:
    class edge:
        def __init__(self, to, rev, cap):
            self.to, self.rev, self.cap = to, rev, cap

    def __init__(self, v):
        self.V = v
        self.G = [[] for i in xrange(self.V)]

    def add(self, frm, to, cap):
        self.G[frm].append(self.edge(to, len(self.G[to]), cap))
        self.G[to].append(self.edge(frm, len(self.G[frm]) - 1, 0))

    def add_dual(self, frm, to, cap):
        self.G[frm].append(self.edge(to, len(self.G[to]), cap))
        self.G[to].append(self.edge(frm, len(self.G[frm]) - 1, cap))

    def bfs(self, s):
        self.level = [-1] * self.V
        self.level[s] = 0
        que = []
        que.append(s)
        while (que):
            v = que.pop(0)
            for i in xrange(len(self.G[v])):
                e = self.G[v][i];
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[v] + 1;
                    que.append(e.to)


    def dfs(self, v, t, f):
        if v == t: return f
        for i in xrange(self.itr[v], len(self.G[v])):
            self.itr[v] = i
            e = self.G[v][i]
            if e.cap > 0 and self.level[v] < self.level[e.to]:
                d = self.dfs(e.to, t, min(f, e.cap))
                if d > 0:
                    e.cap -= d
                    self.G[e.to][e.rev].cap += d
                    return d
        return 0

    def max_flow(self, s, t):
        inf = float("inf")
        flow = 0
        while 1:
            self.bfs(s)
            if self.level[t] < 0: return flow

            self.itr = [0] * self.V
            f = self.dfs(s, t, inf)
            while f > 0:
                flow += f
                f = self.dfs(s, t, inf)


W, N = int(raw_input()), int(raw_input())
J = map(int, raw_input().split())
M = int(raw_input())
C = map(int, raw_input().split())

mf = MaxFlowDinic(201)

for i in xrange(N):
    mf.add(0, i + 1, J[i])

for i in xrange(M):
    mf.add(100 + i, 200, C[i])

NG = [[False] * M for i in xrange(N)]
for i in xrange(M):
    QX = map(int, raw_input().split())
    for j in QX[1:]:
        NG[j - 1][i] = True
    for j in xrange(N):
        if not NG[j][i]:
            mf.add(j + 1, 100 + i, float("inf"))

cut = mf.max_flow(0, 200)
print "SHIROBAKO" if cut >= W else "BANSAKUTSUKITA"
0