結果

問題 No.2713 Just Solitaire
コンテスト
ユーザー detteiuu
提出日時 2024-10-08 08:38:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 2,390 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-10-08 08:38:37
合計ジャッジ時間 3,932 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

from types import GeneratorType
from collections import deque

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

class Dinic_edge:
    def __init__(self, t, cap, rev):
        self.t = t
        self.cap = cap
        self.rev = rev

class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, u, v, cap):
        self.G[u].append(Dinic_edge(v, cap, len(self.G[v])))
        self.G[v].append(Dinic_edge(u, 0, len(self.G[u])-1))
    
    def bfs(self, s, to):
        self.level = [-1]*self.N
        que = deque()
        que.append(s)
        self.level[s] = 0
        while que:
            n = que.popleft()
            for v in self.G[n]:
                if v.cap and self.level[v.t] == -1:
                    self.level[v.t] = self.level[n]+1
                    que.append(v.t)
        return self.level[to] != -1

    @bootstrap
    def dfs(self, n, to, f):
        if n == to:
            yield f
        for v in self.it[n]:
            if v.cap and self.level[n] < self.level[v.t]:
                d = yield self.dfs(v.t, to, min(f, v.cap))
                if d:
                    v.cap -= d
                    self.G[v.t][v.rev].cap += d
                    yield d
        yield 0
    
    def flow(self, s, t):
        flow = 0
        INF = 10**18
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
bonus = [list(map(int, input().split()))[1:] for _ in range(M)]

D = Dinic(N+2+M)
INF = 10**18
for i in range(N):
    D.add_edge(N+M, i, A[i])
    D.add_edge(i, N+M+1, 0)
for i, C in enumerate(bonus):
    for c in C:
        D.add_edge(c-1, N+i, INF)
for i in range(M):
    D.add_edge(N+i, N+M+1, B[i])

print(-(D.flow(N+M, N+M+1)-sum(B)))
0