結果

問題 No.2713 Just Solitaire
コンテスト
ユーザー navel_tos
提出日時 2024-03-31 17:16:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 83 ms / 2,000 ms
コード長 4,601 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 78,300 KB
最終ジャッジ日時 2024-09-30 21:09:34
合計ジャッジ時間 3,126 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#MMA Contest 018 H

#最大流(stack DFS)
from collections import deque                    # 最大流  V: 頂点数
import sys; sys.setrecursionlimit(10**7)         # 燃やす埋めるにも対応
class maxflow:                                   #  S → A →  
    def __init__(self,V):                        #  ↓   ↓  ↓
        self.V=V                                 #    → B → G
        self.G=[[] for _ in range(V)]            # で、Sが残す頂点とする。このとき、
                                                 # Aを切るならBも切る、は A→B(inf)でOK
    def add_edge(self,u,v,c):                    #
        self.G[u].append([v,c,len(self.G[v])  ]) # Gには [移動先の頂点, 容量, 逆辺の位置] 
        self.G[v].append([u,0,len(self.G[u])-1]) # G[u][辺番号] でアクセス可。逆辺は容量0
                                                 #
    def BFS(self,s):                             #
        D=[-1]*self.V; D[s]=0; Q=deque([s])      #
        while Q:                                 #
            now=Q.popleft()                      #
            for nxt,cap,_ in self.G[now]:        # 容量が残っている辺のみを有効辺とする
                if cap>0 and D[nxt]<0:           #
                    D[nxt]=D[now]+1              #
                    Q.append(nxt)                #
        return D                                 #

    def stackDFS(self,start,fin,total,removed,D):# この頂点以遠の最大流量を考える
        flow=0; Q=[(start,total,False)]          # stack DFS: 再帰の代わりにstackを使う
        while Q:                                 #
            v,tf,back=Q.pop()                    # removed[v]: 頂点vの削除した辺数
            if v==fin: flow=tf; continue         # ゴールした場合はmax flowを流す
            if back and flow:                    # 入りがけか出がけかは変数backで管理
                nxt,_,rev=self.G[v][removed[v]]  #
                self.G[v][removed[v]][1]-=flow   # このDFSでゴールに到達した場合
                self.G[nxt][rev][1]+=flow        # 変数flowがTrueとなり、この流量を流す
                continue                         #
            if back: removed[v]+=1               # 逆にゴールできなかった場合は辺を削除
            while removed[v]<len(self.G[v]):     # なので1回のDFSごとに1個の辺が削除される
                nxt,cap,rev=self.G[v][removed[v]]#
                if cap>0 and D[v]<D[nxt]:        #
                    Q.append((v,tf,1))           #
                    Q.append((nxt,min(tf,cap),0))#
                    break                        #
                else: removed[v]+=1              #
        return flow                              #
                                                 #
    def Calc_max(self,s,fin):                    #
        flow=0                                   #
        while True:                              # 操作1: BFSで辺を引き直す
            D=self.BFS(s)                        # 配列Dは毎回作り直す
            if D[fin]<0: return flow             # これ以上流せなくなった場合は解を出力
            removed=[0]*self.V                   # removed配列はBFSするたびに作り直す
            while True:                          # 操作2: DFSで最短距離のフローを流す
                f=self.stackDFS(s,fin,10**18,removed,D)
                if f==0: break                   # 最短距離でフローが流せなくなったらbreak
                flow+=f                          # 操作1に戻り反復 お疲れ様でした



#入力受取
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

#N + M + 2頂点の頂点を用意
#Sを不採用  Gを採用側として最小カットに帰着する
MF = maxflow(N + M + 2)
S, G = N + M, N + M + 1

#1. カードiを採用すると罰金A[i]円
for i in range(N):
    MF.add_edge(i, G, A[i])
    
#2. 先にsum(B)円もらっておくが、i種類目のボーナスを使わないと罰金B[i]円
for i in range(M):
    _, *C = map(lambda x: int(x) - 1, input().split())
    MF.add_edge(S, N + i, B[i])

    #3. i種類目のボーナスを使うなら、必ずCのボーナスも使う側に回す
    #   S → A, B → G でAをSから切るならBも切る、は A→B(inf)でOK
    for j in C:
        MF.add_edge(N + i, j, 10 ** 18)

#罰金の最小カットを求める
print( sum(B) - MF.Calc_max(S, G) )
0